1. 문제

[Silver II] 연결 요소의 개수 - 11724

문제 링크

성능 요약

메모리: 250828 KB, 시간: 728 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

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

입력

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

출력

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

2. 풀이

import sys
sys.setrecursionlimit(10000)

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

num = []
for _ in range(M):
    num.append(list(map(int, input().split())))

graph = [[] for _ in range(N + 1)]

for i, j in num:    
    graph[i] += [j]
    graph[j] += [i]
    
visit = [0 for _ in range(N + 1)]

cnt = 0

def dfs(i):
    global cnt
    
    if visit[i] == 1:
        return False

    visit[i] = 1
    for j in graph[i]:
        if visit[j] == 0:
            visit[j] = 1
            dfs(j)
        else:
            return False # 연결되어 있다면(방문한 적이 있다면) False를 return
    return True
            
for i in range(1, N + 1):
    if dfs(i) == True:
        cnt += 1

print(cnt)