并查集是一种用来管理元素分组情况的数据结构。可以高效地进行如下操作。

1.查询元素a和元素b是否属于同一组

2.合并元素a和元素b所在的组

 

并查集也是使用树形结构实现的。

每个元素对应一个节点，每个组对应一棵树。在并查集中，哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注，整体组成一个树形结构才是重要的。

 

(1) 初始化

准备n个节点来表示n个元素。最开始时没有边。

(2) 合并

从一个组的根向另一个组的根连边，这样两棵树就变成了一棵树，也就把连个组合并为一个组了。

(3) 查询

为了查询两个节点是否属于同一组，我们需要沿着树向上走，来查询包含这个元素的树的根是谁。

如果两个节点走到了同一个根，那么就可以知道它们属于同一组。

在下图中，元素2和元素5都走到了元素1，因此它们属于同一组。

另一方面，由于元素7走到了元素6，因此与元素2和元素5属于不同组。

注意点

为了避免退化情况的发生，采取如下方法。

1.对于每棵树，记录这棵树的高度

2.合并时如果两棵树的rank不同，那么从rank小的向rank大的连边

此外，通过路径压缩，可以使得并查集更加高效。对于每个节点，一旦向上走到了一次根节点，就把这个点到父亲的边改为直接相连边。

在此之上，不仅仅是所查询的节点，在查询过程中向上经过的所有的节点，都改为直接连到根上。

这样再次查询这些节点时，就可以很快知道是谁了。

在使用这种简化的方法时，为了简单起见，即使树的高度发生变化，我们也不修改rank的值。

 

实现如下。par[]表示的是父亲的编号，par[x]=x时，x是所在的树的根。

1 #include
      
        2 using namespace std; 3 int par[100];   //父亲 4 int rank[100];  //树的高度 5  6 //初始化n个元素 7 void init(int n) 8 { 9     for(int i=0; i
      

 

看个题目 食物链(POJ 1182)

分析如下 来自《挑战程序设计竞赛》

1 #include
      
        2 using namespace std; 3 int par[100];   //父亲 4 int rank[100];  //树的高度 5  6 //初始化n个元素 7 void init(int n) 8 { 9     for(int i=0; i
       
        >n>>k;47     //初始化并查集48     //元素x,x+n,x+2*n分别代表x-A,x_B,x-C49     init(n*3);50     for(int i=0;i
        
         >T[i]>>X[i]>>Y[i];53 54         int x=X[i]-1,y=Y[i]-1; //把输入变成0~n-1的范围55         if(x<0||x>=n||y<0||y>=n)56         {57             ans++;58             continue;59         }60 61         if(T[i]==1)//x和y属于同一类 的信息62         {63             if(same(x,y+n)||same(x,y+2*n))64             {65                 ans++;66             }67             else68             {69                 unite(x,y);70                 unite(x+n,y+n);71                 unite(x+2*n,y+2*n);72             }73         }74         else//x吃y 的信息75         {76             if(same(x,y)||same(x,y+2*n))77             {78                 ans++;79             }80             else81             {82                 unite(x,y+n);83                 unite(x+n,y+2*n);84                 unite(x+2*n,y);85             }86         }87     }88     cout<
         
          <