Quick Syntax
csharp
var sets = new DisjointSet(elementCount: 5);
bool merged = sets.Union(1, 3);
bool connected = sets.Find(1) == sets.Find(3);연결 여부를 반복 확인하고 간선을 추가하며 집합을 합칠 때 사용합니다. 경로 자체나 최단 거리를 구하는 구조는 아니며, 경로 압축과 size·rank 결합을 함께 써야 합니다.
구조
유니온-파인드는 여러 원소가 어떤 집합에 속하는지 관리합니다. 핵심 연산은 대표를 찾는 Find와 두 집합을 합치는 Union입니다.
text
Find(x): x가 속한 집합의 대표 찾기
Union(a, b): a와 b가 속한 집합 합치기처음에는 각 원소가 자기 자신을 대표로 갖습니다. 아래 구현은 0-based id 0부터 elementCount - 1까지를 받습니다.
csharp
sealed class DisjointSet
{
private readonly int[] parent;
private readonly int[] size;
public DisjointSet(int elementCount)
{
if (elementCount < 0) throw new ArgumentOutOfRangeException(nameof(elementCount));
parent = new int[elementCount];
size = new int[elementCount];
for (int i = 0; i < elementCount; i++)
{
parent[i] = i;
size[i] = 1;
}
}
public int Find(int value)
{
if ((uint)value >= (uint)parent.Length) throw new ArgumentOutOfRangeException(nameof(value));
int root = value;
while (parent[root] != root) root = parent[root];
while (parent[value] != value)
{
int next = parent[value];
parent[value] = root;
value = next;
}
return root;
}
public bool Union(int a, int b)
{
int rootA = Find(a);
int rootB = Find(b);
if (rootA == rootB) return false;
if (size[rootA] < size[rootB]) (rootA, rootB) = (rootB, rootA);
parent[rootB] = rootA;
size[rootA] += size[rootB];
return true;
}
}경로 압축
Find를 호출하면서 지나간 노드의 parent를 대표로 바로 연결하면 다음 탐색이 빨라집니다.
text
1 -> 2 -> 3 -> 4
Find(1) 후
1 -> 4, 2 -> 4, 3 -> 4랭크나 크기 기준으로 작은 트리를 큰 트리 아래 붙이면 높이가 커지는 것을 줄일 수 있습니다.
언제 쓰나
| 상황 | 판단 |
|---|---|
| 두 원소가 같은 그룹인지 반복 확인 | 유니온-파인드 |
| 연결 요소를 점진적으로 합침 | 유니온-파인드 |
| 무방향 그래프 사이클 감지 | Union 실패 여부 확인 |
| 크루스칼 MST | 간선 정렬 + 유니온-파인드 |
| 경로 자체가 필요 | BFS, DFS 검토 |
Union(a, b)에서 이미 같은 대표라면 두 정점은 이미 연결되어 있습니다. 무방향 그래프에서 새 간선이 사이클을 만드는지 확인할 때 이 성질을 씁니다.
주의할 점
유니온-파인드는 연결 여부를 빠르게 알려주지만, 실제 경로나 거리 정보는 알려주지 않습니다. “어떻게 연결되어 있는가”가 필요하면 그래프 탐색이 필요합니다.
경로 압축과 크기 기준 합치기를 함께 쓰면 연산 하나의 상환 비용은 사실상 상수에 가까운 O(α(n))입니다. 과거 시점으로 되돌리는 rollback DSU가 필요하면 parent 변경 기록을 남겨야 하므로, 이 구현처럼 경로를 압축하면 안 됩니다.
참고 링크
1 sources