今天給SDUT的ACMer看了看并查集，總結(jié)總結(jié)下：
并查集，干的就是“并”和“查”兩件事。很多與集合相關(guān)的操作都可以用并查集高效的解決。
int Find(int x)
{
if (tree[x].parent != x)
{
tree[x].parent = Find(tree[x].parent);
}
return tree[x].parent;
}
void Merge(int a, int b, int p, int q, int d)
{
if (tree[q].depth > tree[p].depth) tree[p].parent = q;
else
{
tree[q].parent = p;
if (tree[p].depth == tree[q].depth) tree[p].depth++;
}
}
其中Find()函數(shù)用了路徑壓縮優(yōu)化，而Merge()函數(shù)用了啟發(fā)式合并的優(yōu)化(個(gè)人感覺有了路徑壓縮，啟發(fā)式合并優(yōu)化的效果并不明顯，而經(jīng)常因?yàn)轭}目和代碼的限制，啟發(fā)式合并會(huì)被我們省略)。
有個(gè)問(wèn)題，如何求節(jié)點(diǎn)到跟節(jié)點(diǎn)的距離？