<2022모각코/TIL> [백준/python] 11724 - 연결 요소 개수

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True
            dfs(i)

count = 0
for i in range(1, n+1):
    if visited[i] == False:
        count+=1
        dfs(i)

print(count)

알고리즘: dfs를 활용해서 푸는 문제이다. x y를 저렇게 나눠서 append 하는 이유는 이것이 방향이 없는 그래프임으로 x와 y모두 넣어줘야하기 때문이다. 인접 리스트로 만든다음에 dfs를 시행하고, dfs를 나와 False가 되면 count를 하나 올려주는 형식이다.

 

dfs의 이해를 도와준 문제. 아직도 근데 잘 이해가 되지 않는다..