11724. 연결 요소의 개수

업데이트 시간 : 2025-06-27 06:43:34 +0000

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

문제 링크

성능 요약

메모리: 66100 KB, 시간: 1144 ms

분류

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

제출 일자

2025년 6월 27일 15:43:09

문제 설명

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

입력

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

출력

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

💡 Solutions

📄 연결 요소의 개수.py

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n, m= map(int, input().split())

node = [ [] for _ in range(n+1)]
is_visited = [ False for _ in range(n+1)]

for _ in range(m):
    u, v = map(int, input().split())
    node[u].append(v)
    node[v].append(u)

# print(node)

def dfs(start, is_visited):
    if is_visited[start]:
        return 0
    
    is_visited[start] = True
    
    for idx in node[start]:
        dfs(idx, is_visited)
        
    return 1
cnt = 0
for i in range(1, n+1):
    cnt += dfs(i, is_visited)

print(cnt)