updata 2024.10.21 加入了路径压缩的非递归写法

学习笔记，仅供参考，未经允许，禁止转载

厚着脸皮求个小红心

一，并查集概念

引例1:

•有N个计算机中心，开始时都是独立的。后来不断的架设了M条网线，每条网线把其中的2个计算机中心连接起来。
•直接或间接连接的计算机中心都可以相互通信，组成一个网络。
•问有多少个连通网络？

引例2:

•围棋的棋子有黑色和白色两种，相同颜色的棋子如果是上下或左右相邻的，则称这两个棋子是连通的，直接或间接连通的棋子称为一块棋。
•现在，不断给出N个落棋子的信息(颜色、横坐标、纵坐标)，问棋盘上有多少块棋？

在以上两个例子中，我们可以画出以下一个图

然后并查集就是在这其中进行查找和处理

二，并查集（一）：暴力处理

还是上面那张图。

假设我们要连接3和4两个点，但是他们是在同一个连通块，不用处理

但假如是连接5和2两个点，他们不在同一个连通块，怎么办？
凉拌

我们可以给每个点添上一个id，不同连通块内的点的id是不同的，例如↓↓↓

如果我们要连接5和2两个点，相当于把两个连通块连接在了一起，所以要把其中一个连通块的id改成另外一个连通块的id
代码块：

int f[105],n,m,ans;//每个点的id，ans记录连通块个数
cin>>n>>m;//n为点的个数，m为连接线
for(int i=1;i<=n;i++)
    f[i]=i;//初始时每个点单独为一个连通块
ans=n;
for(int i=1;i<=m;i++)
{
    int x,y;
    cin>>x>>y;//要连接的两个点
    if(f[x]!=f[y])
    {
         for(int j=1;j<=n;j++)
            if(f[j]==f[x]) f[j]=f[y];//如果与x同一个连通块就全都加入y的连通块
    }
}
时间复杂度为O(nm);

三，优化

1.路径压缩

话说天下大乱，各大武林高手层出不穷，许多大师为满足自己的野心，当起了帮主，招兵买马，讨伐四路诸侯......
额，跑题了，回归正题
一开始，全天下只有n个武林高手，他们唯我独尊，只认自己为帮主
（蓝色箭头指向的为自己的上司）

后来，1打赢了3，于是3就认1为帮主

就这样，各方势力互相打斗，最后，城了这个样子↓↓↓

后来，有人想知道2的帮主是谁，去问了2，他说他的帮主是4，又去问了4，他说他的帮助是3，双去问了3，3又说他的帮助是1，这才知道了2的帮助是1
后来那人就想，如果问4的时候，就告诉2他的帮助是3，去问3的时候，就告诉2和4他们的帮主是1，那这样岂不是所有人都知道武林盟主是谁了？

其实，在上面的故事中，最终江湖上的情况可以表示成一棵树

然后，如果想要查找2或者5的老大，就要搜3次，但是我们可以把树拆解成下面这个样子

这样只用搜一次！
每次搜索的时候，如果不是以自己为父节点的，返回自己，否则将自己的父节点设置成自己的父节点的父节点，就像下面这样

int find(x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}

这就是我们的路径压缩

2，按秩合并
秩：通常指树的高度
这里就直接举个例子

如果要连接7和8，你是会选择8当7的父节点还是7当8的父节点？
当然是7当8的父节点！因为如果8当7的父节点的话，原本1的搜索次数就会由3变成4
这就是按秩排序的思想：短的认长的为父节点，使得长的那棵树长度不变，维护好底部树根的搜索次数
当然这东西实际上屁用没有，一般用路径压缩就够了

四，代码

int find(x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy) a[fx].fa=fy;
 } 

五，非递归版路径压缩

先讲一个悲伤的故事：

在XX学校信息队，一次比赛时，我们的老师给出了一套题目

一个人熟练的用路径压缩解决了一道题目

但是，他RE了，无缘校队第一

没错由于我们的路径压缩是用递归实现的，是有可能爆栈空间的

因此我们应该用非递归版的

int findfa(int x)
{
    int ro,y,k;
    ro=x;
    while(ro!=fa[ro])
        ro=fa[ro];//优先找到根节点
    y=x;
    while(y!=ro)
    {
        k=fa[y];//用k暂存
        fa[y]=ro;//路径压缩
        y=k;//上跳到父节点
    }
    return ro;
}