졍's 기술 블로그

연결 요소의 개수

티어 : Silver 2
시간 제한 : 3 초
메모리 제한 : 512 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

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

입력

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

출력

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

예제 입출력

Algorithm

DFS 이용
1. 그래프 구성
    ➝ 양방향으로 구성
2. DFS 구현해 덩어리가 하나씩 나올 때마다 COUNT += 1

Code

import sys
input = sys.stdin.readline


def dfs(start):

    # 현재 Node가 이미 방문한 Node라면 False Return
    if visited[start]:
        return False
    
    # 현재 Node 방문 처리
    visited[start] = True

    # 이웃노드 중
    for x in graph[start]:
        # 방문하지 않은 노드만 접근
        if visited[x] == False:
            dfs(x)
            
    return True
    
    
# 입력
N, M = map(int, input().split())
sys.setrecursionlimit(10**9)
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

# 노드 하나씩 보면서 덩어리 count
count = 0
for x in range(1, N+1):
    if not visited[x] and dfs(x):
        count += 1
        
print(count)

메모리: 64880 KB
시간: 768 ms