[Data Structure] Union Find

Union-Find는 집합을 다루는 트리 형태의 자료구조다. Union 함수를 통해 집합을 서로 결합시키고 Find를 통해 그 집합의 대표 정점을 가져온다. Union-Find 는 Kruskal 알고리즘을 구현하는 것에 사용된다. 물론 그 외에도 많이 사용된다.


#include <iostream>
#include <stdio.h>
#define MAX_VETICES 100

using namespace std;

int parent[MAX_VETICES];
int num[MAX_VETICES];

void set_init(int n)
{
for (int i = 0; i < n; i++){
parent[i] = -1;
num[i] = 1;
}
}

int set_find(int vertex)
{
int p, i = -1;
for (i = vertex; (p = parent[i]) >= 0; i = p);
int s = i;
for (i = vertex; (p = parent[i]) >= 0; i = p){
parent[i] = s;
}
return s;
}

void set_union(int s1, int s2)
{
int p1 = set_find(s1);
int p2 = set_find(s2);
if (num[p1] < num[p2]){
parent[p1] = p2;
num[p2] += num[p1];
}
else{
parent[p2] = p1;
num[p1] += num[p2];
}
}

int main()
{
// Suppose Set S = {1,2,3,4,5,6};
set_init(7);

set_union(1, 4);
set_union(5, 2);
// {1,4}, {5,2}, {3}, {6}
for (int i = 1; i <= 6; i++){
printf("Parent of [%d] : %d\n",i, set_find(i));
}

set_union(4, 5);
set_union(3, 6);
// {1,4,5,2}, {3,6}
for (int i = 1; i <= 6; i++){
printf("Parent of [%d] : %d\n", i, set_find(i));
}
return 0;
}