2 月 7 日算法练习- 数据结构-并查集

并查集

并查集是一种图形数据结构，用于存储图中结点的连通关系。
每个结点有一个父亲，可以理解为“一只伸出去的手”，会指向另外一个点，初始时指向自己。
一个点的根节点是该点的父亲的父亲的的父亲，直到某个点的父亲是自己 根
当两个点的根相同时，我们就说他们是属于同一类，或者说是连通的。
如下：7、5、1、3、6的根都是3，所以他们是连通的，2、4是连通的，而2、6不连通，因为他们的根不 同

找根

找根的方法是：
如果当前点不是根，就返回父亲的根。否则就是自己。
用递归的方法实现

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

合并

在并查集中，所有的操作都在根上，假如我要使得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）。如下图，执行一次root（7）之后，沿途的点都会直接指向根3。

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

蓝桥幼儿园

#include<iostream>
using namespace std;
const int N = 2e5+9;
int pre[N],n,m;

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

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

修改数组

思路：并查集的查询修改特性，根是未重复的数，非根是重复的数。初始化并查集 pre[i]=i表示每个根都未重复，遍历数组 a，遍历到 x 时将 x 修改为root(x) 的根，将 root(x) 指向 root(x+1) 的根，表示 x 的过去根已经重复，新根未重复。

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N],pre[N];

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

int main( ){
    int n;cin>>n;
    for(int i=1;i<=N;i++)pre[i]=i;
    
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i] = root(a[i]);
        pre[a[i]] = root(a[i]+1);
    }
    
    for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[n==i];
    return 0;
}