Union Find(합집합 찾기)

Union Find는 그래프 알고리즘이며, 서로소 집합(Disjoint Set)알고리즘이라고도 한다. 여러개의 노드가 존재할때 서로 다른 두개의 노드가 현재 같은 노드에 속하는지 안하는지 판별하기 위한 알고리즘이다.

노드를 맨처음에 자기 자신을 가르키도록 만들어주고, 노드와 노드가 합쳐졌다는 것을 보여줄 때 가장 작은 노드 값을 가지게 된다. 또한 재귀함수를 사용하여 가장 작은 노드값으로 병합될때까지 알고리즘을 수행하게 된다.

Union Find Code

#include <iostream>
using namespace std;
//부모를 찾는 함수 
int getParent(int parent[], int x)
{
	if(parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}
//두 부모 노드를 합치는 함수 
int unionParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a < b) parent[b] = a;
	else parent[a] = b;
}
//두 노드의 부모가 같은지 다른지 찾아내는 함수 
int findParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a == b) return 1;
	return 0;
}

int main()
{
	int parent[11];
	for(int i = 1 ; i <= 10 ; i++ )
	{
		parent[i] = i;
	}
	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);
	
	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);
	unionParent(parent, 7, 8);
	
	printf("1과 2는 연결되어 있나 %d\n", findParent(parent, 1, 2));
	unionParent(parent, 3, 7);
	printf("3과 7는 연결되어 있나 %d\n", findParent(parent, 1, 2));
	
	return 0;
}

이미지 링크
자료 링크