연결요소의개수 (백준 11724)

연결 요소의 개수 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5

1 2

2 5

5 1

3 4

4 6

예제 출력 1

2

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

11724번: 연결 요소의 개수

---

import sys
sys.setrecursionlimit(10 ** 6) # python 재귀 제한
read = sys.stdin.readline

n, m = map(int, read().split())
graph = [[0 for i in range(n + 1)] for j in range(n + 1)]

for i in range(m):
    a, b = map(int, read().split())
    graph[a][b] = 1
    graph[b][a] = 1

visited = [0] * (n + 1)
count = 0

def dfs(v, visited):
    visited[v] = 1
    for i in range(n + 1):
        if visited[i] == 0 and graph[v][i] == 1:
            dfs(i, visited)

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

print(count)

재귀 제한 걸리지않게 setrecursionlimit 해주기