[백준] 11724번 연결 요소의 개수 해설 및 풀이 (Python)

백준 11724번 연결 요소의 개수

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

 

---

문제

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

입력

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

출력

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

---

문제 유형

그래프 이론

그래프 탐색

너비 우선 탐색

깊이 우선 탐색

 

풀이 방법 도출

 

무방향 그래프에서 한 정점에서 다른 정점으로 경로가 존재하면 같은 연결 요소에 속합니다.

경로가 전혀 없는 정점들끼리는 다른 연결 요소입니다.

 

1. 유니온 파인드를 사용해서 각 정점이 어떤 집합인지, 즉 연결 요소에 속하는지 확인합니다.
2. 모든 간선을 통해 union 연산을 수행하면 연결된 정점들은 같은 집합에 속하게 됩니다.
3. 마지막에 모든 정점에 대해서 그들의 최상위 부모를 찾아서 중복을 제거한 뒤, 연결 요소의 개수를 세면 됩니다.

 

시간 복잡도

• 초기화 : O(N)
• union 연산 : O(1)
• find 연산 : O(1)
• 총 시간 복잡도 : O(N + M)

---

핵심 코드 삽입 및 설명

 

import sys

# find 연산
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])  # 경로 압축
    return parent[x]

# union 연산
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    return parent

input = sys.stdin.readline
n, m = map(int, input().split())  # 정점 수 n, 간선 수 m
parent = [i for i in range(n + 1)]  # 자기 자신을 부모로 초기화
edges = []

# 간선 입력 및 union 연산
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))
    union_parent(parent, u, v)

# 연결 요소의 개수를 세기 위해 모든 정점의 최종 부모를 찾음
connected_components = set()
for i in range(1, n + 1):
    connected_components.add(find_parent(parent, i))

print(len(connected_components))