算法之并查集

并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合

关于并查集是什么我们在这里不作详细讲解，我们直接学习其中操作，如果你对并查集不了解，请自行去查找

一.合并：

我们将两个集合合并在一起模版：

//并查集:
const int N = 1e3;
int fa[N], sz[N], dep[N];
int findset(int x)
{
	if (x == fa[x])
		return x;
	else
		return findset(fa[x]);
}
void Union(int x, int y)
{
	int fx = findset(x), fy =findset(y);
	if (fx == fy)
		return;
	else
		fa[fx] = fy;//我们这里默认将fx合并到fy
}

二.路径压缩：

我们可以将一个长链压缩成右图：

好处：可以大大减少合并次数

模版：

//路径压缩;
int findset(int x)
{
	if (fa[x] == x)
		return x;
	fa[x] = findset(fa[x]);
	return fa[x];
}

//简写
int findset2(int x)
{
	return x == fa[x] ? x : (fa[x] == findset2(fa[x]));
}

三.按size合并

模版：

const int N = 1e3;
int fa[N], sz[N], dep[N];
//启发式合并;
//size合并;
void Union(int x, int y)
{
	int fx = fa[x], fy = fa[y];
	if (fx == fy)
		return;
	if (sz[fx] > sz[fy])//默认是将fx合并到fy，所以我们如果size：fx>fy，可以交换fx fy，这样和默认就一样了
		swap(fx, fy);
	fa[fx] = fy;//默认是将fx合并到fy
	sz[fy] += sz[fx];//fx合并到fy后，fy上元素个数会增加sz[fx]个
}

四.按深度合并：

//按深度合并
void Union(int x, int y)
{
	int fx = fa[x], fy = fa[y];
	if (fx == fy)
		return;
	if (dep[fx] > dep[fy])
		swap(fx, fy);
	fa[fx] = fy;
	if (dep[fx] == dep[fy])//注意：只有两个深度相同时，合并总深度才会增大
		dep[fy]++;
}

以上就是我们关于并查集的模版

你学会了吗？现在通过这题来测试下吧：

【模板】并查集 - 洛谷

我的解答：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,z,x,y;
int fa[N];

int findset(int x)
{
    if(fa[x]==x)
    return x;
    fa[x]=findset(fa[x]);
    return fa[x];
}

int main()
{
    //取消同步流
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //输入
    cin>>n>>m;
    //构造并查集
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>z>>x>>y;
        if(z==1)//合并操作
        {
            int fx=findset(x),fy=findset(y);
            if(fx==fy)
                continue;
            else
                fa[fx]=fy;
        }
        else//查询操作
        {
            int fx=findset(x),fy=findset(y);
            if(fx==fy)
                cout<<'Y'<<endl;
            else
                cout<<'N'<<endl;
        }
    }
    return 0;
    
}

下面给一道练习题：

亲戚 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int N=1e4;
int a[N];

int findset(int x)
{
    if(a[x]==x)
        return x;
    a[x]=findset(a[x]);
    return a[x];
}


int main()
{
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)
        a[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        //并查集
        int fx=findset(x),fy=findset(y);
        if(fx==fy)
            continue;
        else
            a[fx]=fy;
    }
    for(int i=1;i<=p;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        //并查集
        int fx=findset(x),fy=findset(y);
        if(fx==fy)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

最后，感谢大家的支持！！！