1，介绍并查集

         并查集是一种图形数据结构，用于存储图中节点的连通关系。
         每个节点都有一个父亲可以理解为“一支伸出去的手”，会指向另外一个点，初始时指向自己
 一个点的根节点是该点的父亲的父亲的……的父亲，直到某个节点的父亲是自己（根），当两个节点相同时，我们就说他们是属于同一类，或者说是连通的。
         如下：7--->5--->1--->3<---6      4--->2
         7 5 1 3 6 d的根都是3，所以他们是连通的，2 6不连通，因为他们的根不同
         找根：如果当前点不是根，就返回父亲的根，否则就是自己
         关键变量：pre[] 是一个数组，pre[x] 表示节点 x 的父节点。用递归的方法实现

​
int root(int x)
{
    if (pre[x] == x) return x;
    return root(pre[x]);
}

/*递归逻辑：
终止条件：若 pre[x] == x，说明 x 是根节点，直接返回。
递归查找：否则，继续递归查找 pre[x] 的根节点。*/

2， 并查集----合并
         在并查集中，所有的操作都在根上，假如我要使得x，y两个点合并，只需要将root(x)指向root(y)，或使得root(y)指向root(x).
 pre[root(x)]=root(y);
         例如我要合并4和6，则需要将2指向3或将3指向2。
         路径压缩：找根的函数的复杂度最坏情况下会达到o(n)，如果查询次数较多的话效率会非常低下，我们可以在找根的过程中，将父亲直接指向根，从而实现路径压缩，这样可以使得找根的总体时间复杂度接近：
 o(1),如  1-->   3   <--5
             ^| ^| ^|
         4--->2  7  6
代码：

int root(int x)
{
    return pre[x] = (pre[x] == x ? x : root(pre[x]));//最后这一步不能写成root(x)
    //因为这是一次递归！！！要寻找真正的根！
}
//查找元素 x 所在集合的根节点，并在查找过程中压缩路径，使后续查找更快。
//如果x是根的话就直接返回x，否则就将x的父节点设置为（直接指向）真正的根！

模板题：蓝桥杯官网——蓝桥幼儿园

第1行包含两个正整数 N,M其中 N 表示蓝桥幼儿园的学生数量，学生的编号分别为 1∼N。

之后的第 2∼M+1 行每行输入三个整数，op,x,y：

• 如果 op=1，表示小明用红绳连接了学生 x 和学生 y 。
• 如果 op=2，请你回答小明学生 x 和 学生 y 是否为朋友（用红绳牵住的才是朋友）。

1≤N,M≤2×105，1≤x,y≤N

代码：

#include <iostream>
using namespace std;
const int N=2e5+9;
int pre[N];
//路径压缩:都指向根
int root(int x)
{
  return pre[x]=(pre[x]==x?x:root(pre[x]));
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n,q;cin>>n>>q;
  //初始化
  for(int i=1;i<=n;i++) pre[i]=i;
  while(q--)
  {
    int op,x,y;cin>>op>>x>>y;
    if(op==1) pre[root(x)]=root(y);
    else cout<<(root(x)==root(y)?"YES":"NO")<<'\n';
  }
  return 0;
}

3,并查集启发式合并

         并查集启发式合并是一种启发式算法。
         启发式算法是一种用于解决优化问题的算法，它们依赖于直观或者经验来制定解决问题的策略，通常用于那些没有有效算法或者问题规模太大而是精确算法不切实际的情况。
         有些启发式算法是可以证明复杂度的，有些则是可以用来优化的。
         例如A*算法，分支界限算法（大三 算法设计与分析）都是在决策时计算评估函数，从而尽可能快的找到答案，但是无法证明其复杂度。
         启发式合并就是每次将较小的集合合并到较大的集合当中。
         例如假设我们有n(n<=2e5)个集合，第i个集合仅有一个元素i，现在要进行n次合并，每次将两个集合合并，如何操作才能使得时间复杂度合理？
         对于两个集合s1，s2假设size(s1)<=size(s2),那么每次合并后的大小必然>=2size(s1),
 而集合最大也才n个元素，于是对于每个元素，其移动次数不超过logn次。
         例：按秩合并，就是合并时将rank（秩）较小的点指向rank较大的点，而不是所以得合并。
         秩：联通块的最大深度如果采用按秩合并，就不需要路径压缩了，合并和查询（root函数）的时间复杂度就变为了o(logn),并且按秩合并的数不会像路径压缩那样随意具有更强的树的性质
 但实际上按秩合并并没有启发式合并好写，而复杂度是一样的。启发式合并就是在合并的时候将size小的点指向size大的点，size：联通块的大小，所以就用启发式合并。

下面看具体操作。

1.初始化：由于启发式合并增加了一个新的量：联通块的大小（声明为：int siz[N]）于是我们要在初始化的时候加一句话，来将所有的siz初始化为1

​
 for(int i=1;i<=n;i++)pre[i]=i,siz[i]=1;

​ /*pre 数组：传统并查集的父节点数组，pre[i]表示元素 i 的父节点，初始时每个元素的父节点是自身
siz 数组：新增的 "联通块大小" 数组，siz[i]表示以 i 为根的集合中元素的数量
初始化逻辑：每个元素初始时独立成集，因此每个集合的大小都是 1*/

 2.找根函数：由于使用了启发式合并，所以找根函数不需要路径压缩，不然会破坏树的结构
 找根函数：

int root(int x)
{
    return pre[x] == x ? x : root(pre[x]);
}
/*与传统并查集的区别：没有使用路径压缩
传统并查集会在查找时将路径上的节点直接指向根节点（路径压缩），以扁平化树结构
启发式合并中若使用路径压缩，会破坏树的大小关系，导致siz数组无法准确反映集合大小*/

3.合并函数：启发式合并的时候根据siz的大小判断链接方向即可

void merge(int x, int y)
{
    int rx = root(x), ry = root(y);
    if (rx == ry)return;//已经联通，无需处理
    //如果rx更大，则交换，可以保证siz[rx]<=siz[ry]
    if (siz[rx] > siz[ry])swap(rx, ry);
    /*小集合并入大集合：
若 rx 的集合更大（siz[rx] > siz[ry]），交换 rx 和 ry，确保 rx 是较小的集合
将较小集合的根节点 rx 的父节点指向较大集合的根节点 ry
更新较大集合的大小：siz[ry] += siz[rx*/

    // 此时有siz[rx]<=siz[ry],所以一定是rx--->ry
    pre[rx] = ry;
    siz[ry] += siz[rx];
    // 操作完成后rx将不在作为根，于是它的siz也没有意义了，也不会变化了
}
/*启发式合并的核心思想
启发式合并的核心思想是：在合并两个集合时，将较小的集合合并到较大的集合中，
以此保证树的高度不会过快增长，从而优化后续操作的时间复杂度。*/

例题1：蓝桥幼儿园（就是上面那一道）

#include <iostream>
using namespace std;
const int N=2e5+9;
//方法二：启发式合并
int pre[N],siz[N];
//找根函数
int root(int x)
{
  return pre[x]==x?x:root(pre[x]);
}
//合并函数
void merge(int x,int y)
{
  int rx=root(x),ry=root(y);
  if(rx==ry)return;
  //要将小集合并入大集合，所以要判断
  if(siz[x]>siz[y])swap(rx,ry);//将变量进行交换
  //此时rx------>ry
  pre[rx]=ry;
  siz[ry]+=siz[rx];
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n,m;cin>>n>>m;
  for(int i=1;i<=n;i++)pre[i]=i,siz[i]=1;
  while(m--)
  {
    int op,x,y;cin>>op>>x>>y;
    if(op==1)
    {
      merge(x,y);
    }
    else
    {
      cout<<(root(x)==root(y)?"YES":"NO")<<'\n';
    }
  }
  return 0;
}

例题2：蓝桥杯官网——聚合一块

小蓝上完图论课后，小桥给了他一个挑战：

存在 n 个点，m 条边，每条边连接两个点，例如存在一条边为 (ui,vi)，代表有一条边连接了 (ui,vi)两个点。

小桥请小蓝回答，最少加上多少边，可以使得只剩下一个连通块。

连通块：如果某两个点能通过边直接或者间接相连，我们称他们处于一个连通块。

输入格式

第一行输入两个整数 n,m。

接下面 m 行，每行两个整数 ui,vi。

2≤n,m≤105,1≤ui​,vi​≤n。

代码：方法一：通过siz计算联通块法

//在合并联通块后，将原来被合并的联通块清零，最后计算有多少联通块！
//联通块的数量-1就是要合并的线段数量！
#include <iostream>
using namespace std;
const int N=1e5+9;
int siz[N],pre[N];

int root(int x)
{
  return pre[x]==x?x:root(pre[x]);
}

void merge(int x,int y)
{
  int rx=root(x),ry=root(y);
  if(rx==ry) return;
  if(siz[x]>siz[y]) swap(rx,ry);
  pre[rx]=ry;
  //siz[y]+=siz[x];忘了是对根操作！
  siz[ry]+=siz[rx];
  siz[rx]=0;
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int ans=0;
  int n,m;cin>>n>>m;
  for(int i=1;i<=n;i++) pre[i]=i,siz[i]=1;//初始化！！！
  //为什么可以这样写？
  //因为题目数据1≤ui,vi<=n
  while(m--)
  {
    int x,y;cin>>x>>y;
    merge(x,y);
  }
  for(const auto&i:siz)
  {
    if(i) ans++;
  }
  cout<<ans-1<<'\n';
  return 0;
}

方法二：通过找根来计算联通块

//在合并联通块后，将原来被合并的联通块清零，最后计算有多少联通块！
//联通块的数量-1就是要合并的线段数量！
#include <iostream>
using namespace std;
const int N=1e5+9;
int siz[N],pre[N];

int root(int x)
{
  return pre[x]==x?x:root(pre[x]);
}

void merge(int x,int y)
{
  int rx=root(x),ry=root(y);
  if(rx==ry) return;
  if(siz[x]>siz[y]) swap(rx,ry);
  pre[rx]=ry;
  //siz[y]+=siz[x];忘了是对根操作！
  siz[ry]+=siz[rx];
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int ans=0;
  int n,m;cin>>n>>m;
  for(int i=1;i<=n;i++) pre[i]=i,siz[i]=1;//初始化！！！
  //为什么可以这样写？
  //因为题目数据1≤ui,vi<=n
  while(m--)
  {
    int x,y;cin>>x>>y;
    merge(x,y);
  }
  //因为在合并完成后，只有根节点的父节点是自己，而ui，vi的数据范围是1~n
  //所以只需遍历1~n，找root(i)==i的数量即可
  for(int i=1;i<=n;i++)
  {
    //if(root(i)==i) ans++;这样写也可以！！！
    if(pre[i]==i) ans++;
  }
  cout<<ans-1<<'\n';
  return 0;
}

例题3 蓝桥杯官网——修改数组

给定一个长度为 N 的数组 A=[A1,A2,⋅⋅⋅,AN]，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2​,A3​,⋅⋅⋅,AN​。

当修改 Ai 时，小明会检查 Ai​ 是否在 A1​ ∼ Ai−1 中出现过。如果出现过，则小明会给 Ai​ 加上 1 ；如果新的 Ai仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai没有在 A1​ ∼ Ai−1 中出现过。

当 AN​ 也经过上述修改之后，显然 A 数组中就没有重复的整数了。

现在给定初始的 A 数组，请你计算出最终的 A 数组。

输入描述

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。

其中，1≤N≤10^5，1≤Ai≤10^6。

输出描述

输出 N 个整数，依次是最终的 A1,A2,⋅⋅⋅,AN。

这一题就不能用启发式合并了，因为要维护其方向性，详细解析见代码：

#include <iostream>
using namespace std;
const int N=1e6+9;
int a[N],pre[N];
int root(int x)
{
  //return pre[x]==x?x:root(pre[x]);
  //要路径压缩提高效率
  return pre[x]=pre[x]==x?x:root(pre[x]);
}
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=1e6;i++) pre[i]=i;
  for(int i=1;i<=n;i++)
  {
    //1，先找到第一个数字的根，此时就是pre[a[i]]即a[i]
    //就是找到大于等于a[i]的最小未使用值v
    int v=root(a[i]);
    //输出这个数
    cout<<v<<' ';
    //标记这个数已经处理过了：方法就是改变它的父节点，指向a[i]+1的根，即pre[a[i]+1]就是a[i]+1
    pre[v]=root(v+1);
    //此时再进行循环，若下一个数已经在前面出现过，假设a[2]=a[1]
    //那么就找v=root(a[2])=root(a[1])=root(a[1]+1)=pre[a[1]+1]
    //于是就输出这个pre[a[1]+1]
    //若下一个数没在之前出现过，就直接输出
  }
  return 0;
}





//优化后：
#include <iostream>
using namespace std;
const int N=2e6+9;
//维护root(i)为>=i且不存在于a[1~i-1]的数字
//若i被使用，则有root(i)=root(i+1)
//左--->右
int pre[N],a[N];
int root(int x)
{
  return pre[x]=pre[x]==x?x:root(pre[x]);//三目操作符少写了x导致错误
}
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;cin>>n;
  for(int i=1;i<=2e6;i++)pre[i]=i;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++)
  {
    cout<<root(a[i])<<' ';
    a[i]=root(a[i]);
    pre[root(a[i])]=root(a[i]+1);
  }
  return 0;
}

OK了，觉得写的不错，就麻烦点赞+关注+收藏吧！！！