11724번 연결 요소의 개수

 

이 문제는 DFS 알고리즘을 이용하여 풀었다.

 

문제풀이

생각보다 단순한 문제다. 입력받은 그대로 그래프를 생성하고, DFS로 그래프를 탐색해서 연결되어 있는 요소가 몇개 인지 확인해서 개수를 출력하면 되는 문제 이다.

 

코드

import sys
sys.setrecursionlimit(10**5)
def graph(x):
    visit[x] = 1
    for y in range(1, N + 1):
        if arr[x][y] == 1 and visit[y] == 0:
            graph(y)

N, M = map(int, sys.stdin.readline().split())
arr = [[0] * (N + 1) for _ in range(N + 1)]; visit = [0 for _ in range(N + 1)]
count = 0
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    arr[u][v] = 1; arr[v][u] = 1
for i in range(1, N+1):
    if visit[i] == 0:
        graph(i)
        count += 1
print(count)