유니온 파인드(Union find) & 서로소 집합(Disjoint Set)?
Union find는 대표적인 그래프 알고리즘으로
집합 내의 요소의 연결성을 효율적으로 추적하는 데 사용되는 데이터 구조 및 알고리즘입니다.
역으로 서로 연결되어 있지 않은 노드를 판별할 수도 있기 때문에 서로소 집합 (Disjoint-set)이라고도 합니다.
알고리즘은 union과 find의 두 가지 연산으로 구성되어 있습니다.
-> union 은 각 노드가 속한 집합을 1개로 합치는 연산
-> find 특정 노드 A에 관해 A가 속한 대표 노드를 반환하는 연산
Union-Find 알고리즘은 집합 내 요소의 연결성을 추적하는 데 유용한 데이터 구조 및 알고리즘입니다.
이것은 많은 그래프 알고리즘에서 사용될 수 있으며 경로 압축 최적화로 O(log n) ~ O(n)의 시간 복잡도를 가집니다.
예제 코드 C++
#include <iostream>
#include <vector>
using namespace std;
// Initialize the parent array
void makeSet(int parent[], int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find the root of the set containing node x
int find(int parent[], int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]); // Path compression
}
return parent[x];
}
// Merge the sets containing nodes x and y
void unite(int parent[], int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
parent[rootY] = rootX; // Make rootX the parent of rootY
}
int n = 5; // Number of nodes
int parent[5]; // Number of nodes
int main() {
makeSet(parent, n); // Initialize the parent array
// Merge sets containing nodes 2 and 4
unite(parent, 2, 4);
// Merge sets containing nodes 1 and 5
unite(parent, 1, 5);
// Merge sets containing nodes 1 and 2
unite(parent, 1, 2);
// Find the set of node 4
int root4 = find(parent, 4);
// Print the parent array
for (int i = 0; i < n; i++) {
cout << parent[i] << " ";
}
cout << endl;
// Print the root of the set containing node 4
cout << "The root of the set containing node 4 is " << root4 << endl;
return 0;
}
백준 예제
https://www.acmicpc.net/problem/1717
#include <iostream>
using namespace std;
constexpr int Max = 1000001;
// 유니온 root노드 배열
int uArr[Max];
int N, M, u, b, c;
//부모를 찾는 함수
//모든 경로가 부모를 가르키게 함
//상수 시간의 복잡도
int Find(int x)
{
if (uArr[x] == x) return x;
return uArr[x] = Find(uArr[x]);
}
//두 노드를 연결 시키는 것
//기준을 정해서 연결시키는 것이 헷갈리지 않음
//작은쪽이 부모 or 큰쪽이 부모
void Union(int x, int y)
{
x = Find(x);
y = Find(y);
if (x != y) {
if (x < y) uArr[y] = x;
else uArr[x] = y;
}
}
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
// 유니온 배열 초기화
for (int i = 0; i <= N; i++) uArr[i] = i;
for (int i = 0; i < M; i++) {
cin >> u >> b >> c;
if (u == 0) { // 합집합 연산
Union(b, c);
}
else { // 질의
if (Find(b) != Find(c)) cout << "NO\n";
else cout << "YES\n";
}
}
return 0;
}
