[알고리즘] 유니온 파인드(Union-Find)

1 유니온 파인드

 유니온 파인드란 어떤 한 노드와 다른 노드가 같은 그래프에 있는지 확인하기 위한 알고리즘이다. 유니온 파인드는 속도를 빠르게 하기 위해서 기존 그래프를 한 개의 노드에 전부 연결된 모양으로 바꾼다. 그러면 2개의 노드가 같은 그래프에 속해 있다면 중심의 노드에 둘 다 연결되어 있을 것이니 중심의 노드가 같은지만 확인하면 된다.

 

 구현 방식은 배열을 이용해서 하게 된다. 배열은 arr[n] 형태로 arr[k](k<=n)에는 중심 노드의 번호가 들어간다. 초기화는 각 노드 번호를 넣는다.

 그래프를 합칠 때는 간선으로 연결된 노드 번호 2개를 받는다.  그리고 각 노드가 연결된 그래프에서의 중심 노드를 찾는다. 중심 노드를 찾는 방법은 배열에서 노드의 번호와 중심 노드의 번호가 같다면 중심 노드이다. 그래서 중심 노드를 찾으면 2개의 중심 노드가 나올건데 만약 둘의 중심 노드의 값이 다르다면 아무거나 정해서 중심 노드 번호를 바꿔서 연결한다.

 같은 그래프인지 볼 때는 간단하다. 배열에서 중심 노드의 번호를 찾고 둘이 같은지만 확인하면 된다. 

2 예제

 위와 같이 노드가 있다. 초기 배열은 arr[6] = { 0, 1, 2, 3, 4, 5}이다.

 노드 1과 노드 2를 연결시켜보겠다. 노드 1과 연결된 중심 노드는 1이고, 노드 2와 연결된 중심 노드는 2이다. 각각의 중심 노드가 다르니 1번을 중심노드로 합치겠다.

arr[6] = { 0, 1, 1, 3, 4, 5}

 노드 2와 노도 3을 연결시켜보겠다. 노드 2와 연결된 중심 노드는 1이고, 노드 3과 연결된 중심 노드는 3이다. 각각의 중심노드가 다르니 1번을 중심노드로 합치겠다.

arr[6] = { 0, 1, 1, 1, 4, 5}

 노드 4와 노드 5를 연결시켜보겠다. 노드 4와 연결된 중심 노드는 4이고, 노드 5와 연결된 중심 노드는 5이다. 각각의 중심 노드가 다르니 4번을 중심노드로 합치겠다.

arr[6] = { 0, 1, 1, 1, 4, 4}

 지금 상태를 그래프로 보면 아래와 같다.

 여기서 2와 5가 연결되었는지 확인해보면 2와 연결된 중심 노드는 1이고, 5와 연결된 중심 노드는 4로 다르니 연결되어 있지 않다는 것을 알 수 있다.

3 코드

https://www.acmicpc.net/problem/1717를 풀 때 사용한 코드이다.

#include <stdio.h>

int arr[1000001] = { 0, };

int Find(int temp) {
	if (arr[temp] == temp)
		return temp;
	else
		return arr[temp] = Find(arr[temp]);
}

void Union(int x, int y) {
	int nx, ny;

	nx = Find(x);
	ny = Find(y);

	if (nx != ny) {
		arr[nx] = ny;
	}
}

int main() {
	int n, m, a, b, c;
	int i, x, y;

	scanf("%d %d", &n, &m);
	for (i = 0; i <= n; i++) {
		arr[i] = i;
	}
	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		
		if (a) {
			x = Find(b);
			y = Find(c);

			if (x == y)
				printf("YES\n");
			else
				printf("NO\n");
		}
		else {
			Union(b, c);
		}
	}

	return 0;
}