[백준] 연결 요소의 개수

연결 요소의 개수

연결 요소의 개수

문제

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

입력

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

출력

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

문제 풀이

import sys


sys.setrecursionlimit(10 ** 6)
# python은 재귀호출 횟수가 1,000회로 제한되어있어서 제한을 늘려준다

N , M = map(int ,sys.stdin.readline().split())
uv = [[False] * (N+1) for _ in range(N+1)]

for i in range(M):
    u, v = map(int, sys.stdin.readline().split())
    uv[u][v] = True
    uv[v][u] = True

ans = 0
chk = [False] * (N+1)

def dfs(i):
    for j in range(1, N+1):
        if uv[i][j] and not chk[j]:
            chk[j] = True
            dfs(j)

for i in range(1, N+1):
    if not chk[i]:
        ans += 1
        chk[i] = True
        dfs(i)

print(ans)

'''
무방향 그래프 = 양방향 그래프
a->b , b->a 가 가능하다

'''