여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘
두 가지 연산
Find
노드 X가 속해있는 집합 반환
Union (합집합)
노드 X가 포함된 집합과 노드 Y가 포함된 집합을 합치는 연산
접근
Union → 그래프의 노드연결
연결 정보가 주어질 경우 집합을 합쳐야 하는 경우
Find → 어느 그래프에 속해있는지
연결 정보를 가지고 어떤 집합에 속해있는지 찾을 때(반대로 속해있지 않은 경우도)
구현
트리 형태 사용
“부모 포인터 표현” 사용
각 노드에 대해 그 노드의 부모에 대한 포인터만 저장
같은 부모 → 같은 집합
1차원 배열로 구현 가능
-1은 부모가 없다는 뜻
배열의 인덱스를 부모에 대한 포인터로 사용
예
-1은 부모가 없거나 자신이 부모인 경우
-1로 초기화된 배열
A
B
C
D
E
F
-1
-1
-1
-1
-1
-1
Union(A, B)
A
B
C
D
E
F
-1
0
-1
-1
-1
-1
Union(A, C)
A
B
C
D
E
F
-1
0
0
-1
-1
-1
Union(B, C)
둘이 부모가 같으므로 아무 일도 일어나지 않음 -> 사이클이 생기지 않음
A
B
C
D
E
F
0
0
0
-1
-1
-1
Union(B, D), Union(E, F)
A
B
C
D
E
F
-1
0
0
1
-1
4
Union(A, F)
A
B
C
D
E
F
-1
0
0
1
0
4
코드
public int[] parents = new int[n];
public void union(int a, int b) {
int root1 = find(a);
int root2 = find(b);
if (root1 != root2) {
if (root2 > root1)
parents[root2] = root1;
else
parents[root1] = root2;
}
}
public int find(int a) {
if(parents[a] == -1)
return a;
return find(parents[a]);
}
