[BOJ] 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. 연결요소의 정의

2. DFS

3. 파이썬 재귀limit 처리

 

- 연결요소는 연결로 갈 수 있는 집합의 개수를 뜻한다.

예제 

6 5

1 2

2 5

5 1

3 4

4 6

 

는 1,2,5  3,4,6 이 다른 집합이므로 2개인것이다.

 

- n이 1000이므로 dfs를 사용해서 같은 집합이면 같은 값으로 마킹해주면된다.

 

- python3으로 제출하면 런타임에러가 나는데, 이는 재귀깊이 제한이 걸려있기 때문이다

(pypyp3는 재귀제한이 없어서 바로 통과한다.)

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

graph = dict()
for i in range(1, 1+n):
    graph[i] = []

for _ in range(m):
    a, b = map(int, input().rstrip().split(" "))
    graph[a].append(b)
    graph[b].append(a)

visited = [0]*(1+n)


def dfs(graph, visited, start, marking):
    visited[start] = marking
    for g in graph[start]:
        if(visited[g] == 0):
            dfs(graph, visited, g, marking)


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

print(len(set(visited[1:])))