← 전체 회차
a-090-number-of-connected-components-in-an-undirected-graph2026-08-18mediumleetcode #323neetcode150

무방향 그래프의 연결 요소 개수

#depth-first-search#breadth-first-search#union-find#graph
↗ leetcode #323 · a-090-number-of-connected-components-in-an-undirected-graph
01

문제

· problem
P.a-090-number-of-connected-components-in-an-undirected-graph

무방향 그래프의 연결 요소 개수

↗ leetcode #323

n개의 노드를 가진 무방향 그래프가 주어집니다. 노드는 0부터 n-1까지 번호가 매겨져 있습니다. 간선 리스트가 주어질 때, 그래프의 연결 요소(connected component)의 개수를 반환하세요. 연결 요소란 두 노드 간의 경로가 존재하는 노드들의 부분집합입니다. 간선이 없는 고립된 노드도 자신만의 연결 요소를 이룹니다.

제약
  • · 1 ≤ n ≤ 2000
  • · 0 ≤ edges.length ≤ n * (n - 1) / 2
  • · 0 ≤ a, b < n
  • · a ≠ b (no self-loops)
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
5
[[0,1],[1,2],[3,4]]
2
example 2input → output
5
[[0,1],[1,2],[2,3],[3,4]]
1
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    간선이 없을 수도 있나요?
  • ☐
    같은 간선이 여러 번 나타날 수 있나요?
  • ☐
    간선의 순서가 최종 답에 영향을 미치나요?
  • ☐
    연결된 노드들의 실제 리스트를 반환해야 하나요?
  • ☐
    무방향 간선 [0,1]은 0→1과 1→0을 동시에 의미하나요?
  • ☐
    노드가 자기 자신과 연결된 간선이 있을 수 있나요?
  • ☐
    모든 노드가 한 번은 간선에 나타나야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· Union-Find 구조 생성
○
dsu = UnionFind()
○
parent = list(range(n))
○
dsu = {}
step 2· 모든 간선 순회
○
for a, b in edges:
○
for a in edges:
○
for i in range(len(edges)):
step 3· 두 노드 연결│ 중첩
○
dsu.union(a, b)
○
dsu.union(a, a)
○
dsu.f[a] = b
step 4· 고유한 부모 개수 세기
○
return len(set(dsu.findParent(x) for x in range(n)))
○
return len(dsu.f)
○
return len([dsu.findParent(x) for x in range(n)])
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class UnionFind:
2
    def __init__(self):
3
        self.f = {}
4
5
    def findParent(self, x):
6
        y = self.f.get(x, x)
7
        if x != y:
8
            y = self.f[x] = self.findParent(y)
9
        return y
10
11
    def union(self, x, y):
12
        self.f[self.findParent(x)] = self.findParent(y)
13
14
15
class Solution:
16
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
17
        dsu = UnionFind()
18
        for a, b in edges:
19
            dsu.union(a, b)
20
        return len(set(dsu.findParent(x) for x in range(n)))
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
5
[[0,1],[1,2],[3,4]]
→
2
case 2
5
[[0,1],[1,2],[2,3],[3,4]]
→
1
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.