[ 그래프 이론-11724 ] 연결 요소의 개수(Python)

---

접근법

dfs를 활용하여 접근하였고, 방문하지 않은 노드에 대하여 dfs를 적용한다면, 연결된 노드들을 방문하고 만약 연결이 안된 다른 그룹이 있다면, 연결 요소의 개수를 증가시키고 다시 dfs를 적용시키면 된다.

---

정답

import sys
sys.setrecursionlimit(10**9)

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

visited = [False]*(M+1)
graph = [[]for _ in range(M+1)]

for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(start):
    visited[start] = True

    for tmp in graph[start]:
        if visited[tmp] == False:
            dfs(tmp)

cnt = 0

for i in range(1,M+1):
    if visited[i] == False:
        cnt += 1
        dfs(i)

print(cnt)