그래프에 연결 요소가 총 몇 개 있는지 카운트하는 문제다.
즉 그래프에서 모든 정점을 다 방문할 때까지 DFS나 BFS로 탐색한 횟수를 세면 된다.
DFS를 사용해서 풀었는데 RecursionError가 발생해서 인위적으로 재귀횟수를 늘리는 코드를 추가했다.
sys.setrecursionlimit(10**6)
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
cnt=0
visited = [False]*(n+1)
graph=[[]for i in range(n+1)]
for i in range(m):
s,e = map(int,input().split())
graph[s].append(e)
graph[e].append(s)
def dfs(v):
visited[v]=True
for i in graph[v]:
if not visited[i]:
dfs(i)
for i in range(1,n+1):
if not visited[i]:
dfs(i)
cnt+=1
print(cnt)
'[BOJ] - Python' 카테고리의 다른 글
[백준] 1525 : 퍼즐 python (0) | 2023.08.19 |
---|---|
[백준] 10451 : 순열 사이클 python (0) | 2023.08.19 |
[백준] 2644 : 촌수계산 python (0) | 2023.08.18 |
[백준] 1389 : 케빈 베이컨의 6단계 법칙 python (0) | 2023.08.18 |
[백준] 2606 : 바이러스 python (0) | 2023.08.17 |