Union-Find (유니온 파인드)

Union: 원소 x가 속한 부분 집합과 원소 y가 속한 부분 집합의 합집합을 구한다.
Find: 원소 x가 속한 부분 집합을 찾는다. (루트 반환)

Union의 가중법칙: 무거운 쪽이 루트가 되도록 하는 방식, 노드 개수가 더 많은 트리에 연결한다.
Find의 경로압축: Find를 수행할 때 x에서 루트까지 가는 경로 상에 있는 노드를 모두 루트의 자식 노드로 만든다.

가중법칙 및 경로압축을 하고 Union을 n-1회, find를 m(>=n)회 하면 대략적으로 O(m)을 만족한다.
위 최적화를 하지 않을 시, 최악의 경우 편향 트리가 만들어져 Find를 1회하는데 O(n)이 소요된다.

Union-Find 최적화 및 비최적화 비교 소스 (Comapare with Optimization & non-optimization)

#include <stdio.h>

#define size 7
typedef struct {
	int parent;
	int count; // '최적화' 에서만 사용
}uf;
typedef uf* ufp;

// 초기 집합 n개 생성
void set_init(ufp u, int n) {
	for (int i = 0; i < n; i++) {
		u[i].parent = -1;
		u[i].count = 1;
	}
}

// curr가 속하는 집합의 루트을 반환한다.
int Find(ufp u, int curr) {
	if (u[curr].parent == -1)
		return curr;
	return Find(u, u[curr].parent);
}

// 두 개의 원소가 속한 집합을 합친다.
void Union(ufp u, int a, int b) {
	int root1 = Find(u, a);
	int root2 = Find(u, b);
	if (root1 != root2)
		u[root2].parent = root1;
}

// Find를 한 뒤 경로압축을 진행한다. 
int comp_Find(ufp u, int curr) {
	if (u[curr].parent == -1)
		return curr;

	// 루트 노드 찾기 
	int tmp = comp_Find(u, u[curr].parent);
	// 경로 압축 (리턴해서 받은 루트 노드의 값을 부모 노드의 값으로 사용)
	// 다음에 comp_Find가 호출되면 순환 횟수가 줄어든다. 
	u[curr].parent = tmp;
	return tmp;
}

// 경로압축과 가중법칙을 적용하여 Union을 한다. 
void fast_Union(ufp u, int a, int b) {
	int root1 = comp_Find(u, a);
	int root2 = comp_Find(u, b);
	int temp = u[root1].count + u[root2].count;

	if (root1 != root2) {
		if (u[root1].count < u[root2].count) {
			u[root1].parent = root2;
			u[root2].count = temp;
		}
		else {
			u[root2].parent = root1;
			u[root1].count = temp;
		}
	}
}

int main() {
	// -----------------비 최적화 코드 사용-------------------------- // 

	// 집합 size개 생성 
	ufp u = (ufp)malloc(sizeof(uf) * size);
	set_init(u, size);

	Union(u, 0, 1); // {0,1},{2},{3},{4},{5},{6}
	Union(u, 2, 3); // {0,1},{2,3},{4},{5},{6}
	Union(u, 4, 5); // {0,1},{2,3},{4,5},{6}
	Union(u, 1, 2); // {0,1,2,3},{4,5},{6}
	Union(u, 3, 4); // {0,1,2,3,4,5},{6}
	Union(u, 5, 6); // {0,1,2,3,4,5,6} 

	// 합집합 결과 보기 <가중 법칙 적용 x>
	printf("\n(비최적화) 합 집합 결과: ");
	for (int i = 0; i < size; i++)
		printf("[%d] ", u[i].parent);
	printf("\n");

	free(u);

	// -----------------최적화 코드 사용-------------------------- // 

	// 집합 size개 생성 
	u = (ufp)malloc(sizeof(uf) * size);
	set_init(u, size);

	fast_Union(u, 0, 1); // {0,1},{2},{3},{4},{5},{6}
	fast_Union(u, 2, 3); // {0,1},{2,3},{4},{5},{6}
	fast_Union(u, 4, 5); // {0,1},{2,3},{4,5},{6}
	fast_Union(u, 1, 2); // {0,1,2,3},{4,5},{6}
	fast_Union(u, 3, 4); // {0,1,2,3,4,5},{6}
	fast_Union(u, 5, 6); // {0,1,2,3,4,5,6} 

	// 합집합 결과 보기 <경로압축 및 가중 법칙 적용>
	printf("\n(최적화) 합 집합 결과: ");
	for (int i = 0; i < size; i++)
		printf("[%d] ", u[i].parent);
	printf("\n");

	free(u);
	return 0;
}