[BOJ]11724. 연결 요소의 개수

문제:

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

입력:

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

출력:

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

풀이방법:

인접리스트와 dfs를 사용해서 이 문제를 사용했다. N, M을 입력받은 뒤에 인접리스트 U를 초기화하고, visited 배열을 초기화 했다. 방문하지 않은 정점에 대해서만 dfs를 수행해서 연결 요소의 개수를 구했다. 

import sys
sys.setrecursionlimit(10000)
 
def dfs(i):
    visited[i]=1
    for n in U[i]:
        if visited[n]==0:
            dfs(n)
 
 
N, M=map(int,input().split())
 
U = [[]for _ in range(N+1)]
visited = [0]*(N+1)
 
for _ in range(M):
    s,e = map(int,input().split())
    U[s].append(e)
    U[e].append(s)
 
answer= 0
for i in range(1,N+1):
    if visited[i]==0:
        answer+=1
        dfs(i)
print(answer)

문제링크:

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

11724번: 연결 요소의 개수