Chapter 5-5 : Tree (Disjointset(Union & Find))

Union은 각각의 tree가 서로 연결되어 있지 않고 독립적으로 있을때 서로 독립되어 있는 tree를 연결시키는 작업입니다.

여기서 Disjointset이란 서로소 집합이란 의미로 서로 집합된 부분에서 중복되는 수가 없어야 합니다.

예를들어 다음과 같은 tree가 있을때 우리는 parent 배열을 만들 수 있습니다.

S1의 Root는 0이고 S2의 Root는 4고 S3의 Root는 2입니다. 따라서 parent 배열에서 인덱스번호 0, 4, 2는 -1입니다. 

즉, 대장이라는 의미입니다.

S1의 자식 node 6, 7, 8은 0을 가리키므로 parent배열 6, 7, 8은 0입니다.

나머지 tree들도 마찬가지 입니다.

---

물론 이렇게 union&find를 할 수 있지만

이번시간에는 ,weighted union을 해보겠습니다. 

말 그대로 node의 개수에 따라 parent 배열을 만드는 것입니다.

위의 tree를 보면 S1은 4개의 node, S2는 3개의 node, S3는 3개의 node를 가지고 있습니다.

따라서 배열 parent 인덱스 0, 4, 2는 각각의 node갯수를 갖습니다.

여기서 합칠때는 node의 갯수가 더 많은 쪽으로 붙게 됩니다.

예를 들어 node 0와 node 4가 합쳐질때 4가 0쪽으로 붙게 됩니다.

void weighted_union(int i, int j) {
	int temp = parent[i] + parent[j];
	if (parent[i] > parent[j]) {
		parent[i] = j;
		parent[j] = temp;
	}
	else { 
		parent[j] = i;
		parent[i] = temp;
	}
}

예를들어 i가 0이고 j가 4일 때 

temp는 -7이 됩니다. temp는 둘이 합쳐진 node의 갯수입니다.

i가 j보다 node의 갯수가 많으므로 else문으로 들어가게 됩니다.

따라서 parent[j] = i  ==> parent[4] = 0 이됩니다. 

즉, 4번 node는 0 번 node의 자식으로 들어가게 됩니다.

마지막으로 parent[i] = temp 이므로 parent[0] = -7이 됩니다.