[11724] 연결 요소의 개수

더 탐색할 노드가 있는지 확인하기 위해

빈 visited 가 아닌 → 꽉 차있는 tovisit set으로 바꿨다.

 

기본적으로 tovisit에서 pop한 값을 togo에 넣어서 dfs 돌린다.

 

tovisited의 key들은 간선이 있는 node들이므로

간선이 없는 node는

if N > len(tovisit): connected_component += N - len(tovisit)

으로 해결한다.

import sys

N, M = map(int,sys.stdin.readline().split())
graph = dict()

for m in range(M):
    u, v = map(int,sys.stdin.readline().split())
    if graph.get(u)==None:
        graph[u] = [v]
    else:
        graph[u].append(v)
    if graph.get(v)==None:
        graph[v] = [u]
    else:
        graph[v].append(u)

tovisit = set(graph.keys())

# print(graph)
# print(tovisit)

togo = list()
connected_component = 0

if N > len(tovisit):
    connected_component += N - len(tovisit)

while tovisit:
    togo.append(tovisit.pop())
    connected_component += 1
    while togo:
        node = togo.pop()   
        tovisit.discard(node)
        for next in graph[node]:
            if next in tovisit:
                togo.append(next)

print(connected_component)