서로소 집합(Disjoint-set)

• 서로소 집합 : 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.
• 집합에 속한 하나의 특정 멤버(representative) 를 통해 각 집합들을 구분한다.
• 상호배타 집합을 표현하는 방법 : 연결리스트, 트리
• 상호배타 집합 연산 : Make-Set(x), Find-Set(x), Union(x, y)

---

CODE

1.  Make-Set(x)

void makeSet(int x) {
	parents[x] = x;
}

 

2. Find-Set(x)

int findSet(int x) {
	if(x == parents[x]) return x;
	else {
		parents[x] = findSet(parents[x]);
		return findSet(parents[x]);
	}
}

3. Union(x, y)

void union(int x, int y) {
	int px = findSet(x);
	int py = findSet(y);
	if( rank[px] > rank[py] ) {
		parents[py] = px;
	} else {
		parents[px] =py;
		if(rank[px] == rank[py]) {
			rank[py]++;
		}
	}
}