Union-Find 알고리즘

• 합집합 찾기(Union-Find), 서로소 집합(Disjoint-Set) 알고리즘

여러 개의 노드 중 두 개의 노드를 선택해서, 이 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다.

 

 

1. 우선 모든 노드가 연결되지 않고 자신만을 집합의 원소를 갖고있도록 만듭니다. 따라서 모든 값이 자기 자신을 가리키도록 합니다.

 

첫 번째 행은 노드 번호, 두 번째 행은 부모 노드 번호입니다. 즉, 각 노드 번호가 어떤 부모에 포함되어 있는지를 의미합니다.

1	2	3	4	5
1	2	3	4	5

 

2. 1번 노드와 2번 노드가 연결되어있다고 가정합시다. 

1	2	3	4	5
1	1	3	4	5

 

부모를 합칠 때에는 더 작은 값 쪽으로 합치는 것(Union)이 일반적입니다.

따라서 1번 노드와 2번 노드가 연결되면 2번 노드의 부모 노드 번호가 1이 됩니다.

 

3. 2번 노드와 3번 노드도 연결되어있다고 가정합시다.

그렇다면 아래와 같이 됩니다.

1	2	3	4	5
1	1	2	4	5

 

4. 노드 1번과 노드 3번이 연결 되어있는지 체크합니다.

그러나 1의 부모는 1, 3의 부모는 2로 다르기 때문에 부모 노드만 보고는 파악할 수가 없습니다. 

3의 부모를 찾기 위해 3이 가리키고 있는 2를 찾고, 2의 부모가 1이므로 결론적으로 3의 부모는 1임을 알 수 있습니다.

이 과정을 재귀 함수를 이용해 구현합니다. 이러한 union 연산이 다 수행되면 아래와 같이 표가 작성됩니다.

1	2	3	4	5
1	1	1	4	5

즉 노드 1,2,3번의 부모가 모두 1이기 때문에 세 노드는 같은 그래프에 속한다고 할 수 있습니다.

---

• 관련 문제

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

---

• 소스 코드

#include<iostream>
using namespace std;

int parent[1000001];
int n, m;

int getParent(int x)
{
	if (parent[x] == x) return x;
	else return parent[x] = getParent(parent[x]);
}

void unionParent(int x, int y)
{
	x = getParent(x);
	y = getParent(y);

	if (x < y) parent[y] = x;
	else parent[x] = y;


}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);//입출력 번갈아 나타날 경우에 필수
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
	}
	int u, a, b;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> a >> b;
		if (!u)
		{
			unionParent(a, b);
		}
		else
		{
			if (getParent(a) == getParent(b))
			{
				cout << "yes\n";
			}
			else
			{
				cout << "no\n";
			}
		}
	}
	return 0;
}