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

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

11724번: 연결 요소의 개수

 

1. 코드설명

1-1 재귀

sys.setrecursionlimit(10**6)

def dfs(i):

    done[i]=1

    for j in arr[i]:

        if done[j]==0:

            dfs(j)

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

arr = [[] for i in range(n+1)]

for i in range(m):

    a,b = map(int,input().split())

    arr[a].append(b)

    arr[b].append(a)

    

cnt = 0

done=[0]*(n+1)

for i in range(1,n+1):

    if done[i]==0:

        dfs(i)

        cnt+=1

print(cnt)

 

1-2

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

dic = {i : [] for i in range(1, N+1)}

for _ in range(M):

    a, b = map(int, input().split())

    dic[a].append(b)

    dic[b].append(a)

visited = [0] * (N + 1)

ans = 0

for i in range(1, N+1):

    if visited[i] == 1 : continue

    else :

        visited[i] = 1

        ans += 1

        to_do = [i]

        while to_do : 

            x = to_do.pop()

            for y in dic[x]:

                if visited[y] == 0:

                    visited[y] = 1

                    to_do.append(y)

print(ans)

 

2. 주의사항

재귀의 경우

sys.setrecursionlimit(10**6) 으로 반복의 깊이를 지정해 주지 않으면 오류가 발생한다.