今天给SDUT的ACMer看了看并查集,总结总结下:
并查集,干的就是“并”和“查”两件事。很多与集合相关的操作都可以用并查集高效的解决。
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()函数用了路径压缩优化,而Merge()函数用了启发式合并的优化(个人感觉有了路径压缩,启发式合并优化的效果并不明显,而经常因为题目和代码的限制,启发式合并会被我们省略)。
有个问题,如何求节点到跟节点的距离?