Как посчитать количество компонент связности неориентированного невзвешеннего графа?

Question

Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности.

Тесты:

входные данные:
6 4
3 1
1 2
5 4
2 3
выходные данные:
3

входные данные:
6 4
4 2
1 4
6 4
3 6
выходные данные:
2

И мой код:

inp =list(map(int,input().split()))
n,m = inp[0],inp[1]
 
def ToDict(n,m):
    ribs = list()
    while m > 0:
        ribs.append(list(map(int, input().split())))
        m -= 1
    ribsDict = dict()
    for i in range(n):
        currRibs = []
        for j in range(len(ribs)):
            if ribs[j][0] == i + 1:
                currRibs.append(ribs[j][1])
            elif ribs[j][1] == i + 1:
                currRibs.append(ribs[j][0])
        ribsDict[i + 1] = currRibs
    return ribsDict
 
 
ribsDict = ToDict(n,m)
 
Visited = [False]*(n + 1)
 
 
def DFS(start,verts):
    Visited[start] = True
    verts.append(start)
    for u in ribsDict[start]:
        if not Visited[u]:
            DFS(u,verts)
    return verts
 
comps = list()
 
for i in range(1,n+1):
    if not Visited[i]:
        comps.append(DFS(i,list()))
 
print(len(comps))

Он работает, но я не понимаю как его можно сделать быстрее?

Answer 1

Написал свой код с учетом своих же рекомендаций по оптимизации:

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n)]
for i in range(m):
    u, v = [int(i) - 1 for i in input().split()]
    graph[u].append(v)
    graph[v].append(u)

visited = [False] * n
answer = 0

for i in range(n):
    if visited[i]:
        continue

    answer += 1
    visited[i] = True
    queue = [i]
    while queue:
        v = queue.pop()
        for to in graph[v]:
            if not visited[to]:
                visited[to] = True
                queue.append(to)
            
print(answer)

То есть был использован ускоренный ввод, граф считывается нормально и в лист, дфс написан в нерекурсивной форме.

БЛОГ НА HUSL

Как посчитать количество компонент связности неориентированного невзвешеннего графа?

Ответы (1 шт):