Disjoint Set

Disjoint Set，不相交集，也叫并查集

Union/Find算法：
Find：它返回包含给定元素的集合。
Union：合并两个集合。

用数组来模拟树。
初始化时，数组元素为0。正数的表示父亲是谁，如图：


Union优化：每个根的数组元素包含它的树的高度的负值，按树的高度合并，这样任何节点的深度均不会超过 logN。
第一个数组图是按大小合并，第二个数组图是按高度合并。

按树高度合并代码

typedef int DisjSet[128];
typedef int SetType;
typedef int ElementType;

void SetUnion(DisjSet S, SetType Root1, SetType Root2)
{
	if (S[Root2] < S[Root1]) /* Root2 is deeper set */
		S[Root1] = Root2;	/* Make Root2 new root */
	else
	{
		if (S[Root1] == S[Root2])  /* Same height, */
			S[Root1]--;           /* so update */
		S[Root2] = Root1;
	}
}

Find优化：路径压缩，每执行一次Find操作，从X到根的路径上的每一个节点都使它的父节点变成根。
路径压缩与按大小合并完全兼容，但不完全与按高度合并兼容，此时，可用估计的高度(秩)。

SetType Find(ElementType X, DisjSet S)
{
	if (S[X] <= 0)
		return X;
	else
		return S[X] = Find(S[X], S); // 与普通Find不同在于多了："S[X] = "
}

来自《数据结构与算法分析》