本文主要向大家介绍了C/C++知识点之并查集，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

 
 在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
如果n比较大，那么反复询问你某个元素所在集合，你该怎么做？
如果每次都遍历，那么显然会超时，那么用一些数据结构比如建树什么的，很可能会空间不够，在这个时候就得用到并查集了。
顾名思义，并查集就是将相同集合的想办法联系在一起，那样查的时候就不用一一遍历来询问它是不是这个集合的了。
例题，畅通工程，大体题意：每行给你俩个数代表路的编号且这俩条路已联通，最后问你还至少需要修几条路使所有路都能够联通。
思路：给每一个联通的集团设定一个老大，而集团成员都存储老大的id，每进来俩相连的成员看他们老大是谁，如果是不同老大就改成相同老大，因为他们是相连的，是一个集团的，那最后看看有多少个老大，那就有多少个集团，那就需要多少条路将这些集团连起来。

 
若要这些集团连起来，只需一个集团的某一个和其他集团有联系就好了，看看实际操作代码吧：
 
int f[MAX+1];    //申请一个数组存储每个成员的老大id
for(int i=1;i<=MAX;i++)
f[i]=i;                               //初始化每个人的老大就是自己               初始化
 
int  _find(int n)              //寻找这个人的老大是谁    
{    if(n!=f[n])
     return _find(f[n]);                                                          查询
    return n;
}
 
a=_find(a1);  b=_find(b1);      //新进来俩有联系的成员，分别查询他们老大是谁
if(a!=b)                       //如果这俩人老大不同，分别属于俩集团的                 联通
{f[a]=b;                       //让一方老大任另一方老大为老大，俩集团从此有联系，合并成一个集团，有共同的一个老大了
 //_find(a); }                                      //下面压缩路径时加这句进行压缩
 
 
int sum=0;                                                                      回答题目问题
 for(int i=1;i<=MAX;i++)               //sum为现在有几个老大，即有几个集团，当然统一局面就是所有人都有一个老大，他们都存储自己上司id，而老大自己存储自己id。
if(f[i]==i)                                                                           
sum++; 
如果要问这俩人是不是一个集团的，直接看他俩老大是不是同一个人。（_find(a)?_find(b)）
 
这样就是并查集的查询，联通，都搞定了。
当然我说的这么简单是没有压缩过路径的，就是所有人都存自己上司的id,寻找老大时需要由上司再问上司，直到老大（老大的特点是存储自己id）,而压缩过路径的就是人们都存它老大的id，问的时候直接看俩人存储的id是否相同（f[a]?f[b]）。
 
压缩路径得加这段代码，很容易看懂的,就在寻找函数上加点就好了：
int _find(int n)
{  int res=n;
  while(n!=f[n])
   n=f[n];              //找到老大id
 int j;
  while(res!=n)
 { j=f[res];
 f[res]=n;             //把从自己开始把上司id都改成老大id
 res=j;}
 return n;            //返回老大
}
   

本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！