DFS - 백준 11724 [Python]

Problem)

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

Solution)

간단하게 인접리스트를 이용해 풀이해주면 된다.

 

Answer)

import sys
sys.setrecursionlimit(10000)
n,m = map(int, input().split()) # 정점, 간선
a = [[] for _ in range(n)]

check = [False]*(n)

for _ in range(m):
    u,v = map(int, input().split()) # 양 끝점
    a[u-1].append(v-1)
    a[v-1].append(u-1)
        
def dfs(x):
    check[x] = True
    for y in a[x]:
        if check[y] == False:
            dfs(y)
            
ans = 0
for i in range(n):
    if not check[i]:
        dfs(i)
        ans+=1
        
print(ans)