并查集(算法与应用)

并查集回炉重造已经有几天了，这次感觉理解更深刻了些，就写篇博客系统梳理一下，别忘了点赞支持下吖家人们

并查集的英文是Disjoint Set Union，缩写为DSU，
直译为不相交集合，即一种不相交集，类似于树的数据结构，又因其可进行的操作有合并与查找，故中文称为并查集。

    1.  组成

并查集主要由一个整型数组和两个函数组成。

数组用于保存对象的根结点，数组下标表示对象序号，数组的值代表该对象的根结点;

一个返回值为整型的find函数，参数为待求根结点的对象序号，返回值为该的对象的根结点。

一个返回值为空的mix函数，参数为两个待合并的对象，调用后完成对两个对象的合并。

    2.  实现

并查集应用时先将各个对象分立，即一人一个不同的根结点，f[i]=i。

查找根结点时应不断调用自身，直至找到f[i]=i，合并两个对象时必须先找到各自的根结点，然后令一个对象的根结点等于另一个对象的根结点。

若遍历数组，记录下满足f[i]=i的对象的数量，此数量即为全部不相交集合的数目。

    3.  代码

#include
using namespace std;
int f[1000000],cnt=0;
int father(int x)
{
  //return f[x]==x?x:father(f[x]);
  if(f[x]==x)return x;           //路径压缩
    return f[x]=father(f[x]);
}
void mix(int x,int y)
{ f[father(x)]=father(y);
}
int main()
{  int i,j,m,n,xx,yy;
   cin>>n>>m;
   for(i=1;i<=n;i++) //开始时各自为独立集合
    f[i]=i;
   for(i=1;i<=m;i++)
   { cin>>j>>xx>>yy;
     if(j==1) mix(xx,yy);//合并到相同集合
   }
   for(i=1;i<=n;i++)
    if(f[i]=i) cnt++;//统计根节点个数
   cout< 
 
 
 
 
分类 
 
 
简单并查集
多个元素，一个关系，元素间有关系则并入同一集合，没有关系则不处理。
 
 
 
种类并查集
多个元素，多种关系，元素间关系可能有传递性，对立性，需建立多个并查集。
 
 
 
带权并查集
类似普通并查集，只是在此基础上为元素的关系赋上权值。
 
 
 
 
 
应用 
 
 
 简单并查集  
 
 
题目：P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 
  
 
 
 
思路：
 
模版题，构造并查集，多次合并再遍历。
 
代码：
 
#include
using namespace std;
int f[1000000];
int father(int x)
{
  //return f[x]==x?x:father(f[x]);
  if(f[x]==x)return x;
    return f[x]=father(f[x]);
}
void mix(int x,int y)
{ f[father(x)]=father(y);
}
int main()
{  int i,j,m,n,xx,yy;
   cin>>n>>m;
   for(i=1;i<=n;i++)
    f[i]=i;
   for(i=1;i<=m;i++)
   { cin>>j>>xx>>yy;
     if(j==1) mix(xx,yy);
     else if(j==2)
     { if(father(xx)==father(yy))
       cout<<"Yn";
       else cout<<"Nn";
     }
   }
}
 
 
 
 种类并查集 
题目：
 
https://www.luogu.com.cn/problem/P1892
 
 
 
 
思路：开二倍数组，一组放朋友，一组放敌人。
 
代码：
 
#include
using namespace std;
int f[100000];
int find(int x)
{ if(f[x]==x) return x;
  return f[x]=find(f[x]);
}
void mix(int y,int x)
{
  f[find(x)]=find (y);
}
int main()
{  int n,m,p,q,i,j,k;
   char c;
   int sum=0,x,y;
   cin>>n>>m;
   for(i=1;i<=n*2;i++)
    f[i]=i;
   for(i=1;i<=m;i++)
     {  cin>>c>>x>>y;
        if(c=='F') mix(y,x);
        else {mix(y,x+n);mix(x,y+n);}
     }
   for(i=1;i<=n;i++)
    {
      if(f[i]==i) sum++;
    }
   cout< 
 
 
 带权并查集 
还没太掌握，以后一定更。。。
 
 
 
 连通块的并查集解决 
题目：https://leetcode-cn.com/problems/number-of-islands/
 
 
 
 
思路：
 
连通块可以理解为无向图中有几个连通的点集，那么这个过程与并查集的原理就极其相似了，将点集看作并查集的祖先和他的后代们，相互连通的点就放在同一祖先下，这样只需要查找共有几个祖先即可。
 
代码：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
 
 
 
 最小生成树的并查集解决 
 
 
题目：P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 
 
 
 
 
 
思路：
 
先把边按照权值进行排序，用贪心的思想优先选取权值较小的边，并依次连接，若出现环则跳过此边（用并查集来判断是否存在环）继续搜，直到已经使用的边的数量比总点数少一即可。
 
代码：
 
#include
#include
#include
#include
#include
using namespace std;
int n,m,i,j,u,v,total;
struct edge{
    int start,to;long long val;
}bian[2000005];
int f[100000];
long long ans;

int find(int x)//并查集部分
{
    if (f[x]==x) return x; else 
    {
        f[x]=find(f[x]);
        return f[x];
    }	
}

bool cmp(edge a,edge b)//结构体快排时用到的
{
    return a.val