首页 > 代码库 > 并查集间单个节点的转移（UVa 11987 Almost Union-Find）

并查集间单个节点的转移（UVa 11987 Almost Union-Find）

2024-08-09 18:43:44   218人阅读

从来没有这么艰难地完成一道算法题过！经过8次失败之后总算提交成功了！所以决定写一篇博文，对并查集的相关内容做一些总结。

普通并查集的操作无非是两种，find_set(x)即找到节点x所在的集合的代表节点，或者是union_set(x,y)，即将x和y所在的两个集合合并起来。如下图所示，有左右两个并集技术分享

通常，我们会选用并查集中父节点为自己的元素作为这个并查集的代表，例如图中的节点a和节点e。那么，我们如何通过集合中的一个节点找到该节点所在集合的代表节点呢？其实很简单，例如上图中的d节点，它首先通过指针找到b，然后b又通过指针找到a，最后发现a的指针是指向自身的，那么a就是该并查集的代表节点了。可是现在有个问题，当一个并查集的节点数非常庞大怎么办？从一个距离代表节点a非常遥远的节点找到a,那递归的层次会变得非常可怕。而且再次查找时又要重复上述的递归过程，因此效率是非常低的。于是，在找到例如d所在集合的代表节点之后，我们就将d的指针直接指向a，而不再指向a了，这就是所谓的路径压缩。这样再下次查找d时只要一次递归就可以了。下面是代码描述：

int find_set(int x)
{
    if(fa[x]!=x)//fa[x]相当于图中的指针，例如，现在图中fa[d]就等于b
        fa[x]=find_set(fa[x]);//路径压缩
    return fa[x];
}

现在该解决两个并查集合并的问题了。从上图中我们可以轻而易举地发现两个并查集合并的规律。其实就是将其中一个并查集的代表节点，如右图中的e，它原本是指向自身的，现在将它指向左边并查集中的一个节点就可以了（并不一定需要如图中所示指向代表节点a）。此时我们再寻找例如g所在的根节点时，它依旧会调用find_set不断向前查找，但是并不会在原来的代表节点e停止递归，因为此时它已经不再指向自身了。最终，f将找到新的代表节点a。那么对于其他节点的操作也是类似的。下面是合并的代码表示：

void union_set(int x,int y)
{
    if(find_set(x)==find_set(y))//已经在同一并查集中
        return;
    else
        fa[find_set(x)]=fa[find_set(y)];//将x所在并查集的代表节点指向y所在并查集的代表节点
    return ;
}

以上这些操作其实都非常简单。但是如果我只想将例如上图中的e节点添加到最左边的那个并查集怎么办？见例题（http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3138）显然，直接将fa[e]等于a是不行的。因为有好多节点指向e，改变了fa[e]，你就要从指向e的所有节点中取出一个代替e作为整个并查集的代表节点，然后将其余指向e的节点指向新的代表节点，而这些操作的时间复杂度将到达0(n)。

那么为什么会出现上述这种情况呢？其实归根到底，原因是我们选取了集合中的一个节点作为代表节点，一旦这个节点不再属于这个集合了，那么整个并查集都将进行调整。因此我们一个非常自然的想法就是，能不能用其他方式来代表一个集合呢？当然可以，如果我们设立一个数组addr[x]专门用来存放并查集的代表节点。而原本指向具体元素的指针fa[x]指向代表节点所在的位置，例如，addr[fa[x]]就是x所在集合的代表节点。当需要将节点x移到y所在的集合时，只要如下操作即可：

fa[x]=fa[y];//改变x指向的代表元素所在的地址
现在，单个节点的删除合并是解决了，那么如何合并整个并查集呢？其实只要将两个并查集的addr[]改成相同就可以了。如下：将地址fa[x]所在的代表元素赋值为fa[y]所在的代表元素。

<pre name="code" class="cpp">addr[fa[x]]=addr[fa[y]];

不过这样做还是会有问题的啦。因为假如,x所在的集合A，和y所在的集合B原先已经合并了。且fa[x]!=fa[y]。那么如上操作addr[fa[x]]是和addr[fa[y]]是相等的。但是，之后再将y所在的集合与z所在的集合C合并。那么addr[fa[y]]=addr[fa[z]]。因为fa[y]!=fa[x]，所以addr[fa[x]]仍旧是原来的数值，而不是addr[fa[z]]。因此真正的合并操作是这样的：
int f1=find_set(addr[fa[x]]),f2=find_set(addr[fa[y]]);
addr[f1]=f2;
当addr[x]!=x的时候，说明两个集合合并了，且将其中一个集合的代表节点所在地址的内容变成了另一个集合代表节点的地址，这一点和基础的并查集操作非常类似。这样，并查集的单个节点的删除合并，以及整体的合并问题就都解决了。
其实核心思想无非是不再用并查集中的一个元素代表整个并查集，这样单个节点的移动就不会对集合中的其他节点带来任何影响。而在集合间的合并操作时，只需将其中一个集合的代表节点指向另一个集合的代表节点了，然后用类似于find_set的操作，就可以找到真正的代表节点了。相信去做一下上面链接的那道题目，理解会更加深刻一些。





并查集间单个节点的转移（UVa 11987 Almost Union-Find）






























        

            
                
                  
                
                

                    联系

                    我们