java数据结构与算法总结(九)--并查集

矫情吗；* 2023-07-19 05:47 12阅读 0赞

[来自百度][Link 1]

并查集，在一些有N个元素的[集合][Link 2]应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的[时间复杂度][Link 3]也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交[集合][Link 2]（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

## 主要操作 ##

初始化

把每个点所在[集合][Link 4]初始化为其自身。

通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，[时间复杂度][Link 5]均为O(N)。

查找

查找元素所在的集合，即根节点。

合并

将两个元素所在的集合合并为一个集合。

通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

## 例题 ##

### Description（题目描述） ###

若某个家族人员过于庞大，要判断两个是否是亲戚，确实不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xzeDIwMTc_size_16_color_FFFFFF_t_70][] ###

### Output（输出） ###

共P行，每行一个’Yes’或’No’。表示第![format_png][]个询问的答案为“有”或“没有”亲戚关系。

### 分析问题实质 ###

初步分析觉得本题是一个[图论][Link 6]中判断两个点是否在同一个连通子图中的问题。对于题目中的样例，以人为点，关系为边，建立[无向图][Link 7]如下：

图0-0-1 \{请补充图解\}

比如判断3和4是否为亲戚时，我们检查3和4是否在同一个连通子图中，结果是在，于是他们是亲戚。又如7和10不在同一个连通子图中，所以他们不是亲戚。

用图的数据结构的最大问题是，我们无法存下多至(M=)2 000 000条边的图，后面关于算法时效等诸多问题就免谈了。

用图表示关系过于“奢侈”了。其实本题只是一个对分离[集合][Link 4]（并查集）操作的问题。

例如样例：

9 7 1
    
    2 4
    
    5 7
    
    1 3
    
    8 9
    
    1 2
    
    5 6
    
    2 3
    
    1 9

我们可以给每个人建立一个集合，集合的元素值有他自己，表示最开始时他不知道任何人是它的亲戚。以后每次给出一个亲戚关系a, b，则a和他的亲戚与b和他的亲戚就互为亲戚了，将a所在集合与b所在集合合并。对于样例数据的操作全过程如下：

初始状态：\{1\} \{2\} \{3\} \{4\} \{5\} \{6\} \{7\} \{8\} \{9\}

输入关系 分离集合

(2,4) \{2,4\}\{1\} \{3\} \{5\} \{6\} \{7\} \{8\} \{9\}

(5,7) \{2,4\} \{5,7\} \{1\} \{3\} \{6\} \{8\} \{9\}

(1,3) \{1,3\} \{2,4\} \{5,7\}\{6\} \{8\} \{9\}

(8,9) \{1,3\} \{2,4\} \{5,7\} \{8,9\}\{6\}

(1,2) \{1,2,3,4\} \{5,7\} \{8,9\}\{6\}

(5,6) \{1,2,3,4\} \{5,6,7\} \{8,9\}

(2,3) \{1,2,3,4\} \{5,6,7\} \{8,9\}

判断亲戚关系

(1,9)，因为1,9不在同一集合内，所以输出"NO"。

最后我们得到3个[集合][Link 4]\{1,2,3,4\}、\{5,6,7\}、\{8,9\}，于是判断两个人是否亲戚的问题就变成判断两个数是否在同一个集合中的问题。如此一来，需要的数据结构就没有图结构那样庞大了。

算法需要以下几个子过程：

(1) 开始时，为每个人建立一个集合FHM\_ak\_ioi(x)；

(2) 得到一个关系a b，合并相应集合FHM\_ak\_noi(a,b)；

(3) 此外我们还需要判断两个人是否在同一个[集合][Link 4]中，这就涉及到如何标识集合的问题。我们可以在每个集合中选一个代表标识集合，因此我们需要一个子过程给出每个集合的代表元FHM\_ak\_csp(a)。于是判断两个人是否在同一个集合中，即两个人是否为亲戚，等价于判断FHM\_ak\_csp(a)=FHM\_ak\_csp(b)。

有了以上子过程的支持，我们就有如下算法。

PROBLEM-Relations(N, M, a1,…,aM, b1,…,bM, Q, c1,…,cQ, d1,…,dQ)

for i←1 to N

do FHM\_ak\_ioi(i)

for i←1 to M

do if FHM\_ak\_csp(ai) != FHM\_ak\_csp(bi)

then FHM\_ak\_noi(ai, bi)

for i←1 to Q

do if FHM\_ak\_csp(ci)=FHM\_ak\_csp(di)

then output “Yes”

else output “No”

解决问题的关键便为选择合适的数据结构实现并查集的操作，使算法的实现效率最高。

### 注意事项 ###

本题的输入数据量很大，这使得我们的程序会在输入中花去不少时间。如果你用Pascal写程序，可以用库函数SetTextBuf为输入文件设置[缓冲区][Link 8]，这可以使输入过程加快不少。如果你是用C语言的话，就不必为此操心了，系统会自动分配缓冲区。

## 单链表实现 ##

一个节点对应一个人，在同一个[集合][Link 4]中的节点串成一条[链表][Link 9]就得到了[单链表][Link 10]的实现。在集合中我们以单链表的第一个节点作为集合的代表元。于是每个节点x（x也是人的编号）应包含这些信息：指向代表元即表首的指针head\[x\]，指向表尾的指针tail\[x\]，下一个节点的指针next\[x\]。

SUB-Make-Set(x)过程设计如下：

SUB-Make-Set(x)

10 head\[x\]←x

11 tail\[x\]←x

12 next\[x\]←NIL

求代表元的SUB-Find-Set(x)过程设计如下：

SUB-Find-Set(x)

13 return head\[x\]

前两个过程比较简单，SUB-Union(a,b)稍微复杂一点。我们要做的是将b所在[链表][Link 9]加到a所在链表尾，然后b所在链表中的所有节点的代表元[指针][Link 11]改指a所在链表的表首节点，如图所示。

图0-0-2

过程的伪代码如下：

SUB-Union(a,b)

14 next\[tail\[head\[a\]\]\]←head\[b\]

15 tail\[head\[a\]\]←tail\[head\[b\]\]

16 p←head\[b\]

17 while p != NIL

18 do head\[p\]←head\[a\]

19 p←next\[p\]

我们来分析一下算法的时间效率。SUB-Make-Set(x)和SUB-Find-Set(x)都只需要O(1)的时间，而SUB-Union(a,b)的时间效率与b所在[链表][Link 9]的长度成线性关系。最坏情况下，即有操作序列SUB-Union(N-1,N), SUB-Union(N-2,N-1), …, SUB-Union(1,2)时，整个算法PROBLEM-Relations的[时间复杂度][Link 5]为O(N+M+N^2+Q)=O(N^2+M+Q)。

由于算法的时间复杂度中O(M+Q)是必需的，因此我们要让算法更快，就要考虑如何使减小O(N^2)。

我们想到合并链表时，我们可以用一种启发式的方法：将较短的表合并到较长表上。为此每个节点中还需包含表的长度的信息。这比较容易实现，我们就不写出[伪代码][Link 12]了。

[时间复杂度][Link 5]。

首先我们给出一个固定对象x的代表元指针head\[x\]被更新次数的[上界][Link 13]。由于每次x的代表元指针被更新时，x必然在较小的[集合][Link 4]中，因此x的代表元指针被更新一次后，集合至少含2个元素。类似地，下一次更新后，集合至少含4个元素，继续下去，当x的代表元指针被更新 log k 次后，集合至少含k个元素，而集合最多含n个元素，所以x的代表元指针至多被更新 log n 次。所以M次SUB-Union(a,b)操作的时间复杂度为O(NlogN+M)。算法总的时间复杂度为O(NlogN+M+Q)。

## 并查集森林 ##

编辑

并查集的另一种更快的实现是用有根树来表示[集合][Link 4]：每棵树表示一个集合，树中的节点对应一个人。图示出了一个并查集森林。

图0-0-3

每个节点x包含这些信息：父节点指针p\[x\]，树的深度rank\[x\]。其中rank\[x\]将用于启发式合并过程。

于是建立集合过程的[时间复杂度][Link 5]依然为O(1)。

SUB-Make-Set(x)

20 p\[x\]←x

21 rank\[x\]←0

用森林的数据结构来实现的最大好处就是降低SUB-Union(a,b)过程的时间复杂度。

SUB-Union(a,b)

22 SUB-Link(SUB-Find-Set(a),SUB-Find-Set(b))

SUB-Link(a,b)

23 p\[a\]←b

合并[集合][Link 4]的工作只是将a所在树的根节点的父节点改为b所在树的根节点。这个操作只需O(1)的时间。而SUB-Union(a,b)的时间效率决定于SUB-Find-Set(x)的快慢。

SUB-Find-Set(x)

24 if x=p\[x\]

25 then return x

26 else return SUB-Find-Set(p\[x\])

这个过程的时效与树的深度成线性关系，因此其平均[时间复杂度][Link 5]为O(logN)，但在最坏情况下（树退化成[链表][Link 9]），时间复杂度为O(N)。于是PROBLEM-Relations最坏情况的时间复杂度为O(N(M+Q))。有必要对算法进行优化。

第一个优化是启发式合并。在优化[单链表][Link 10]时，我们将较短的表链到较长的表尾，在这里我们可以用同样的方法，将深度较小的树指到深度较大的树的根上。这样可以防止树的退化，最坏情况不会出现。SUB-Find-Set(x)的时间复杂度为O(log N)，PROBLEM-Relations时间复杂度为O(N + logN (M+Q))。SUB-Link(a,b)作相应改动。

SUB-Link(a,b)

27 if rank\[a\]>rank

28 then p←a

29 else p\[a\]←b

30 if rank\[a\]=rank

31 then rank←rank+1

然而算法的耗时主要还是花在SUB-Find-Set(x)上。

第二个优化是路径压缩。它非常简单而有效。如图所示，在SUB-Find-Set(1)时，我们“顺便”将节点1, 2, 3的父节点全改为节点4，以后再调用SUB-Find-Set(1)时就只需O(1)的时间。

图0-0-4

于是SUB-Find-Set(x)的代码改为：

SUB-Find-Set(x)

32 if x≠p\[x\]

33 then p\[x\]←SUB-Find-Set(p\[x\])

34 return p\[x\]

该过程首先找到树的根，然后将路径上的所有节点的父节点改为这个根。实现时，递归的程序有许多栈的操作，改成非递归会更快些。

SUB-Find-Set(x)

35 r←x

36 while r≠p\[r\]

37 do r←p\[r\]

38 while x?r

39 do q←p\[x\]

40 p\[x\]←r

41 x←q

42 return r

改进后的算法[时间复杂度][Link 5]的分析十分复杂，如果完整的写出来足可写一节，这里我们只给出结论：改进后的PROBLEM-Relations其时间复杂度为O(N+(M+Q)\*A(M+Q,N))，其中A(M+Q,N)为Ackerman函数的增长极为缓慢的逆函数。你不必了解与Ackerman函数相关的内容，只需知道在任何可想象得到的并查集数据结构的应用中，A(M+Q,N)≤4，因此PROBLEM-Relations的时间复杂度可认为是线性的O(N+M+Q)。

## 优化路径压缩 ##

### 思想 ###

每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快。

### 实现 ###

第一步，找到根结点。

第二步，修改查找路径上的所有节点，将它们都指向根结点。

### 代码 ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    const int M = 1e3 + 10 ;
    
    int n , m ;
    
    int folk[M] ;
    
    int dsu (int u) { 
    
            return u == folk[u] ? u : folk[u] = dsu (folk[u]) ;
    
    }
    
    int main () {
    
            int n ;
    
            scanf ("%d" , &n) ;
    
            for (int i = 0 ; i < n ; i ++) folk[i] = i ;
    
            scanf ("%d" , &m) ;
    
            while (m --) {
    
                    int u , v ;
    
                    scanf ("%d%d" , &u , &v) ;
    
                    int _u = dsu (u) , _v = dsu (v) ;
    
                    if (_u != _v) {
    
                            folk[_v] = _u ;
    
                    }
    
            }
    
            for (int i = 0 ; i < n ; i ++) dsu (i) ;
    
            return 0 ;
    
    }

### 图示 ###

[![format_png 1][]][format_png 1 1]

[![format_png 2][]][format_png 2 1]

## 代码 ##

### Java版 ###

import java.io.BufferedReader;
    
    import java.io.InputStreamReader;
    
    import java.io.StreamTokenizer;
    
    public class Main{
    
        private static int father[];
    
        public static void main(String[]args)throws Exception{
    
                StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
                while(st.nextToken() != StreamTokenizer.TT_EOF){
    
                    int n=(int)st.nval;
    
                    father=new int[n+1];
    
                    for(int i=1;i<=n;i++){
    
                        father[i]=i;
    
                    }
    
                    st.nextToken();
    
                    int m=(int)st.nval;
    
                    st.nextToken();
    
                    int p=(int)st.nval;
    
                    for(int i=0;i<m;i++){
    
                        st.nextToken();
    
                        int a=(int)st.nval;
    
                        st.nextToken();
    
                        int b=(int)st.nval;
    
                        union(a,b);
    
                    }
    
      
    
                    for(int i=0;i<p;i++){
    
                        st.nextToken();
    
                        int a=(int)st.nval;
    
                        st.nextToken();
    
                        int b=(int)st.nval;
    
                        a=findParent(a);
    
                        b=findParent(b);
    
                        System.out.println(a==b?"Yes":"No");
    
                    }
    
                }
    
        }
    
        private static void union(int f,int t){
    
            int a=findParent(f);
    
            int b=findParent(t);
    
            if(a==b)return;
    
            if(a>b){
    
                father[a]=b;
    
            }
    
            else {
    
                father[b]=a;
    
            }
    
        }
    
        private static int findParent(int f){
    
            while(father[f]!=f){
    
                f=father[f];
    
            }
    
            return f;
    
        }
    
    }

### C++版 ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    int n,m,p,FHM_ak_ioi[100005];
    
    /*
    
    x代表例题中的人，FHM_ak_ioi[x]中所存的数代表这一集合中所有人都与一个人有亲戚关系
    
    相当于例题中第一个集合所有的元素都与第一个元素有亲戚关系
    
    搜索时只要找元素所指向的FHM_ak_ioi[x]=x的元素(即父元素)
    
    然后比较两个元素的父元素是否相同就可以判断其关系
    
    */
    
    int findfa(int x){
    
        return (FHM_ak_ioi[x]==x)?x:FHM_ak_ioi[x]=findfa(FHM_ak_ioi[x]);
    
    }
    
    void merge(int x,int y){
    
        FHM_ak_ioi[x]=y;
    
    }
    
    int main(){
    
        scanf("%d%d%d",&n,&m,&p);
    
        for(int i=1;i<=n;i++){
    
            FHM_ak_ioi[i]=i;
    
        }
    
        for(int i=1;i<=m;i++){
    
            int u,v;
    
            scanf("%d%d",&u,&v);
    
            if(findfa(u)!=findfa(v)){
    
                merge(FHM_ak_ioi[u],FHM_ak_ioi[v]);
    
            }
    
        }
    
        for(int i=1;i<=p;i++){
    
            int u,v;
    
            scanf("%d%d",&u,&v);
    
            if(findfa(u)!=findfa(v)){
    
                printf("No\n");
    
            }
    
            else  printf("Yes\n");
    
        }
    
    }

[Link 1]: https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdi
[Link 2]: https://baike.baidu.com/item/%E9%9B%86%E5%90%88/2908117
[Link 3]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057
[Link 4]: https://baike.baidu.com/item/%E9%9B%86%E5%90%88
[Link 5]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xzeDIwMTc_size_16_color_FFFFFF_t_70]: /images/20230528/860dbfd3af284d8fa3bacb6504a8b61c.png
[format_png]: /images/20230528/c4ed4e5d8902479b9e557bad9ad216bd.png
[Link 6]: https://baike.baidu.com/item/%E5%9B%BE%E8%AE%BA
[Link 7]: https://baike.baidu.com/item/%E6%97%A0%E5%90%91%E5%9B%BE
[Link 8]: https://baike.baidu.com/item/%E7%BC%93%E5%86%B2%E5%8C%BA
[Link 9]: https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8
[Link 10]: https://baike.baidu.com/item/%E5%8D%95%E9%93%BE%E8%A1%A8
[Link 11]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88
[Link 12]: https://baike.baidu.com/item/%E4%BC%AA%E4%BB%A3%E7%A0%81
[Link 13]: https://baike.baidu.com/item/%E4%B8%8A%E7%95%8C
[format_png 1]: /images/20230528/9a1c38181ab14198bfd9bcb9f496dd71.png
[format_png 1 1]: https://baike.baidu.com/pic/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442/0/d788d43f8794a4c29ee839550df41bd5ac6e3981?fr=lemma&ct=single
[format_png 2]: /images/20230528/565d5f058b914d77b219469577483737.png
[format_png 2 1]: https://baike.baidu.com/pic/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442/0/aa18972bd40735fa15fb97c79d510fb30f240841?fr=lemma&ct=single