[알고리즘] 분리 집합(Union-Find)

1. 개요

1. 각 노드들을 그룹을 지을 때 사용하는 알고리즘

 

2. 알고리즘 코드

int parent[MAX_G];

int Find(int a)
{
	int pA = parent[a];

	if (pA == a)
		return a;

	return parent[a] = Find(pA);
}

void Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA <= pB)
		parent[pB] = pA;
	else
		parent[pA] = pB;
}

 

3. 문제

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

10775번: 공항