图论之并查集

最近刚刚学习完并查集，有感而发。

这篇仅仅是讲述基础的并查集,不带权值之类的东西。

首先是“查”的操作find()函数

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

其中,fa便是表示祖先。

使用递归算法(不用递归也可以用一个while()循环)，直到找到祖先。

然后是"并"

void U(int x,int y)
{
    int rx=find(x);
    int ry=find(y);
    if(rx!=ry)
    {
        fa[ry]=rx;//合并
    }
}

rx与ry表示的分别是x与y的祖先，当他们两个祖先不同时，合并。

我的合并操作已经写进去了判断祖先是否相等。

自己写的模板题代码

#include
using namespace std;
int fa[10000];
int n,m,z;
int find(int x)
{
    if(fa[x]==x)
    {
        return fa[x]=x;
    }
    else return fa[x]=find(fa[x]);
}
void U(int x,int y)
{
    int rx=find(x);
    int ry=find(y);
    if(rx!=ry)
    {
        fa[ry]=rx;
    }
}
int main()
{
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>z>>a>>b;
        if(z==2)
        {
            if(find(a)==find(b))
            {
                cout<<"Y\n";
            }
            else cout<<"N\n";
        }
        else if(z==1)
        {
            U(a,b);
        }
    }
    return 0;
}

 个人练习题目(洛谷):

P3367

P1551

P1111

P2078

P2256

P2814

P2024