• 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화한다.
• 합치기 (union) : 두 원소 a,b가 주어질 때 이들이 속한 두 집합을 하나로 합친다.
• 찾기 (find) : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환한다.

union과 find를 지원한다고 해서 이 자료 구조를 유니온-파인드 자료 구조라고 부른다.

배열로 구현? 합치기 연산 시 O(n)이 걸림

트리로 구현? 한쪽으로 기울어버릴 경우 높이가 O(n)이 되는 문제가 생길 수 있음 그러나 이는 두 트리를 합칠 때 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣는 방법으로 해결 가능.

find(u)를 통해 u가 속하는 트리의 루트를 찾아냈을 때 parent[u]를 찾아낸 루트로 바꿔 버리는 경로 압축 최적화 가능.

// 트리를 이용해 상호 배제적 집합을 구현한다.
struct OptimizedDisjointSet
{
	vector<int> parent, rank;
	OptimizedDisjointSet(int n) : parent(n), rank(n, 1)
	{
		for (int i = 0; i < n; ++i)
		{
			parent[i] = i;
		}
	}
	
	// u가 속한 트리의 루트의 번호를 반환한다.
	int find(int u)
	{
		if (u == parent[u]) return u;
		return parent[u] = find(parent[u]);
	}
	
	// u가 속한 트리와 v가 속한 트리를 합친다.
	void merge(int u, int v)
	{
		u = find(u); v = find(v);
		// u와 v가 이미 같은 집합에 속하는 경우를 걸러낸다.
		if (u == v) return;
		if (rank[u] > rank[v]) swap(u, v);
		// 이제 rank[v]가 항상 rank[u] 이상이므로 u를 v의 자식으로 넣는다.
		parent[u] = v;
		if (rank[u] == rank[v]) ++rank[v];
	}
};

백준 문제