[백준 / 파이썬] 11724번 연결 요소의 개수

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
no = [list(map(int, input().split())) for _ in range(m)]
am = [[] for _ in range(n+1)]

for u, v in no:
    am[u].append(v)
    am[v].append(u)

c = 0
vi = [0] * (n+1)
def dfs(v):
    vi[v] = 1
    for i in am[v]:
        if not vi[i]:
            dfs(i)
for i in range(1, n+1):
    if not vi[i]:
        dfs(i)
        c += 1
print(c)

 

연결 요소의 개수가 그래프의 개수를 의미

no[u]에 v 저장하고 no[v]에 u 저장

연결요소 개수 저장하는 c 변수를 사용하고 vi에 방문 여부를 검사하도록 한다

for문으로 dfs를 호출을 조정하는 백트래킹 알고리즘 사용