상호 배타적 집합.(Disjoint-set)

설명 잘됨 : http://jinsolkim.kr/50194124086

n명의 사람들이 파티에 왔다고 하자. 레크리에이션 강사가 생일이 같은 사람들끼리 팀을 구성하라고 한다.

사람들이 서로 그룹을 만드는데, 생일이 같은 사람들 찾으면 둘은 한 그룹이 되고 또다른 사람들을

찾아나설것이다. 만약 다른 팀을 찾았는데 생일이 같으면 또 그룹이 합쳐질것이다. 이런것들을 표현하는

자료구조라고 보면 된다. 이를 구현하기 위해 3가지 연산이 필요하다.

1. 초기화, 2. 합치기, 3. 찾기.

따로 상호 배타적 집합으로 쓰이기보다는 최소 신장 트리 등 다른 자료구조의 안에 쓰인다고 한다.

아래 소스코드에 다 구현되있다.

#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

// 트리를 이용해 상호 배제적 집합을 구현한다.
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);
		// 이미 둘이 같은 트리에 속한 경우
		if(u == v) return;
		if(rank[u] > rank[v]) swap(u, v);
		// 이제 항상 rank[v] 가 더 크므로 u 를 v 의 자식으로 넣는다
		if(rank[u] == rank[v]) rank[v]++;
		parent[u] = v;
	}
};
int main() 
{
	OptimizedDisjointSet d(10); //0~9까지의 상호 배타적 집합 만듬.
	d.merge(0,1); //0과 1은 같은 집합이다.
	d.merge(1,2); //1과 2는 같은 집합이다.
	d.merge(2,3); //2와 3은 같은 집합이다. 결국 0,1,2,3은 모두 같은 집합이다.

	cout<<"f = "<<d.find(0)<<endl; //0,1,2,3의 부모를 출력해보면 모두 동일한 부모가 나오는걸 확인할수 있다.
	cout<<"f = "<<d.find(1)<<endl;
	cout<<"f = "<<d.find(2)<<endl;
	cout<<"f = "<<d.find(3)<<endl;
	return 0;
}