并查集

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

作者：

无味 , 2021-04-11 15:57:17 , 所有人可见 , 阅读 500

QQ截图20210411165315.jpg
QQ截图20210411165332.jpg
QQ截图20210411165356.jpg

#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
    for(int i=1;i<=n;++i)
        num[i]=i;
}

int find(int n)//查找
{
    if(n==num[n]) return num[n];
    else find(num[n]);
}

void merge(int a,int b)//合并
{
    int x=find(a);
    int y=find(b);
    num[x]=y;
}
int main()
{
    int t,n,m;
    cin>>t;

    while(t--)
    {
        cin>>n>>m;

        ini(n);//初始化

        while(m--)
        {
            int a,b;
            cin>>a>>b;

            if(find(a)!=find(b))
                merge(a,b);//合并                
        }

        int rec=0;
        for(int i=1;i<=n;++i)
            if(i!=find(i)) rec++;

        cout<<n-rec<<endl;//这个地方要注意

    }
    return 0;
}

算法进阶指南:

#include<iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
void init()
{
    for(int i=1;i<=maxn;++i)//初始化 
        s[i]=i;
}
int find(int x)//查找 
{
    return x==s[x]?x:find(s[x]);
} 
void merge(int x,int y)//合并 
{
    x=find(x);
    y=find(y);
    if(x!=y) s[x]=s[y];
}

int main()
{
    int t,n,m,x,y;
    cin>>t;
    while(t--){
        cin>>n>>m;
        init();
        for(int i=1;i<=m;++i){
            cin>>x>>y;
            merge(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;++i)//统计有多少个集 
            if(s[i]==i)
                ans++;
        cout<<ans<<endl;
    }
}

复杂度:在上述程序中，查找find()、合并merge()的搜索深度是树的长度，复杂度都是O(n),性能较差。下面介绍合并和查询的优化方法，优化之后，查找和合并的复杂度都小于O(${log_2{n}}$).

合并的优化:

在合并元素x和y时先搜到它们的根结点,然后再合并这两个根结点,即把一个根结点的集改成另一个根结点。这两个根结点的高度不同,如果把高度较小的集合并到较大的集上,能减少树的高度。下面是优化后的代码,在初始化时用height[i]定义元素i的高度，在合并时更改。

int height[maxn];
void init(){
    for(int i=1;i<=maxn;++i){
        s[i]=i;
        height[i]=0;//树的高度
    }
}
void merge(int x,int y){//优化合并操作
    x=find(x);
    y=find(y);
    if(height[x]==height[y]){
        height[x]=height[x]+1;//合并，树的高度加一
        s[y]=x;
    }
    else{
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;
    }
}

查询的优化—路径压缩:

程序如下:

int find(int x){
    if(x!=s[x]) s[x]=find(s[x]);//路径压缩
    return s[x];
}
//这样其实还需要递归，但是只递归一次就好了，例如没有路径压缩时，要想求1的根结点，首先要到2-3-4，路径压缩之后，就是1-4.

QQ截图20210411164039.jpg

int find(int x){
    int r=x;
    while(s[r]!=r) r=s[r];//找到根结点
    int i=x,j;
    while(i!=r){
        j=s[i];//用临时变量j记录
        s[i]=r;//把路径上元素的集改为根结点
        i=j;
    }
    return r;
}

最终代码:

#include<iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
int height[maxn];
void init(){
    for(int i=1;i<=maxn;++i){
        s[i]=i;
        height[i]=0;//树的高度
    }
}
int find(int x){
    if(x!=s[x]) s[x]=find(s[x]);//路径压缩
    return s[x];
}
void merge(int x,int y){//优化合并操作
    x=find(x);
    y=find(y);
    if(height[x]=height[y]){
        height[x]=height[x]+1;//合并，树的高度加一
        s[y]=x;
    }
    else{
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;
    }
}

int main()
{
    int t,n,m,x,y;
    cin>>t;
    while(t--){
        cin>>n>>m;
        init();
        for(int i=1;i<=m;++i){
            cin>>x>>y;
            merge(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;++i)//统计有多少个集 
            if(s[i]==i)
                ans++;
        cout<<ans<<endl;
    }
}

POJ 2524.Ubiquitous Religions
刚开始的代码:

#include<iostream>
using namespace std;
const int maxn=50005;
int s[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{

    if(x==s[x]) return s[x];
    else find(s[x]);
}
void merge(int x,int y)
{
    x=find(s[x]);
    y=find(s[y]);
    s[y]=x;
}
int main()
{
    int rec=1;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;

        init(n);

        int a,b,ans=0;
        while(m--)
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }

        for(int i=1;i<=n;++i)
            if(i==s[i]) ans++;

        cout<<"Case "<<rec<<": "<<ans<<endl;
        rec++;
    }
    return 0;
}

提交后显示WA.又看了一下没什么问题。看到n<50000后会不会是TLE了,于是加了个路径优化:

#include<iostream>
using namespace std;
const int maxn=50005;
int s[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{
    if(s[x]!=x) s[x]=find(s[x]);
    else return s[x];
//  if(x==s[x]) return s[x];
//  else find(s[x]);
}
void merge(int x,int y)
{
    x=find(s[x]);
    y=find(s[y]);
    s[y]=x;
}
int main()
{
    int rec=1;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;

        init(n);

        int a,b,ans=0;
        while(m--)
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }

        for(int i=1;i<=n;++i)
            if(i==s[i]) ans++;

        cout<<"Case "<<rec<<": "<<ans<<endl;
        rec++;
    }
    return 0;
}

过了…
这个题还是和hdu1213基本思路一样,难度属于简单题。

AcWing 836. 合并集合

#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
    for(int i=1;i<=n;++i)
        num[i]=i;
}

int find(int n)//查找
{
    if(n==num[n]) return num[n];
    else find(num[n]);
}

void merge(int a,int b)
{
    int x=find(a);
    int y=find(b);
    num[x]=y;
}
int main()
{
    int n,m;
    cin>>n>>m;

    init(n);//初始化

    while(m--)
    {
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='M')
        {
            if(find(a)!=find(b))
                merge(a,b);                
        }
        else
        {
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }


    return 0;
}

查找操作时没加路径优化，TLE了

#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
    for(int i=1;i<=n;++i)
        num[i]=i;
}

int find(int n)//查找
{
     if(n!=num[n])  num[n]=find(num[n]);
     else return num[n];
}

void merge(int a,int b)
{
    int x=find(a);
    int y=find(b);
    num[x]=y;
}
int main()
{
    int n,m;
    cin>>n>>m;

    init(n);//初始化

    while(m--)
    {
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='M')
        {
            if(find(a)!=find(b))
                merge(a,b);                
        }
        else
        {
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }


    return 0;
}

POJ 1611.The Suspects

#include<iostream>
using namespace std;
const int maxn=30005;
int s[maxn];
void init(int n)
{
    for(int i=0;i<maxn;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    else return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    s[y]=x;
}
int main()
{
    int n,m,k;
    int num[maxn];
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        init(n);
        while(m--)//挨个读入每个小组 
        {
            cin>>k;
            int num[maxn];
            for(int i=1;i<=k;++i)
                cin>>num[i];//将每一个小组成员的编号读入数组num中 
            int first=find(num[1]);//用变量first记录小组第一个人的根结点 
            for(int i=2;i<=k;++i)//将小组内成员进行合并 
                if(first!=find(num[i]))
                    merge(first,num[i]);                
        }
        int zero=find(0);//找到0号成员的根结点
        int ans=1;//记录可疑对象的数量 
        for(int i=1;i<n;++i)//遍历整个数组，寻找可疑对象 
            if(find(i)==zero) ans++;

        cout<<ans<<endl;
    }
    return 0;
}

妈的第一次写的时候就是不对，但看了很多次觉着没问题啊.
排查后发现是三个函数写错了，于是照着之前通过的题看了一下原来是find()函数里没有那个else…操

#include<iostream>
using namespace std;
const int maxn=30005;
int s[maxn];
void init(int n)
{
    for(int i=0;i<maxn;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    s[y]=x;
}
int main()
{
    int n,m,k;
    int num[maxn];
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        init(n);
        while(m--)//挨个读入每个小组 
        {
            cin>>k;
            int num[maxn];
            for(int i=1;i<=k;++i)
                cin>>num[i];//将每一个小组成员的编号读入数组num中 
            int first=find(num[1]);//用变量first记录小组第一个人的根结点 
            for(int i=2;i<=k;++i)//将小组内成员进行合并 
                if(first!=find(num[i]))
                    merge(first,num[i]);                
        }
        int zero=find(0);//找到0号成员的根结点
        int ans=1;//记录可疑对象的数量 
        for(int i=1;i<n;++i)//遍历整个数组，寻找可疑对象 
            if(find(i)==zero) ans++;

        cout<<ans<<endl;
    }
    return 0;
}

AcWing 837. 连通块中点的数量

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    s[y]=x;
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            int ans=0;
            for(int i=1;i<=n;++i)
                if(find(a)==find(i)) ans++;

            cout<<ans<<endl;
        }
    }
    return 0;
}

TLE了,对合并进行优化:

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
    {
        s[i]=i;
        height[i]=0;
    }

}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(height[x]==height[y])
    {
        s[y]=x;
        height[x]++;
    }
    else
    {
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            int ans=0;
            for(int i=1;i<=n;++i)
                if(find(a)==find(i)) ans++;

            cout<<ans<<endl;
        }
    }
    return 0;
}

还是TLE
看了一下这个题和上边的最大区别就是对了第三项询问点 a 所在连通块中点的数量
这一块不能简单的进行暴力，要进行优化:
设置一个数组sum[]来存储根结点下有多少个点，在进行合并的时候，顺便更新sum[]数组

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
    {
        s[i]=i;
        height[i]=0;
        sum[i]=1;
    }

}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    sum[x]=sum[x]+sum[y];
    sum[y]=0;
    s[y]=x;
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            cout<<sum[find(a)]<<endl;
        }
    }
    return 0;
}

AC了,再加上合并优化后看看快多少:

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
    {
        s[i]=i;
        height[i]=0;
        sum[i]=1;
    }

}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(height[x]==height[y])
    {
        s[y]=x;
        height[x]++;
        sum[x]+=sum[y];
        sum[y]=0;
    }
    else
    {
        if(height[x]<height[y]) 
        {
            s[x]=y;
            sum[y]+=sum[x];
            sum[x]=0;
        }
        else
        {
            s[y]=x;
            sum[x]+=sum[y];
            sum[y]=0;    
        }
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            cout<<sum[find(a)]<<endl;
        }
    }
    return 0;
}

第一个1122ms，第二个1058ms，还是快一点的

AcWing 2069. 网络分析

#include<iostream>
using namespace std;
const int maxn=10005;
int s[maxn];
long long sum[maxn];
bool initi(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(s[x]);
    y=find(s[y]);
    s[y]=x;
}
int main()
{
    int n,m;
    cin>>n>>m;
    initi(n);

    int c,a,b;
    while(m--)
    {
        cin>>c>>a>>b;
        if(c==1)//连接
            merge(a,b);
        else//发送消息
            for(int i=1;i<=n;++i)
                if(find(i)==find(a)) sum[i]+=b;
    }
    for(int i=1;i<=n;++i)
        cout<<sum[i]<<" ";
    return 0;
}

不出意外,TLE了
下面就要优化将所有和结点p相同根结点的点+t这一操作

1 评论

木石石石_1 2023-01-13 22:49

细，太细了！

App 内打开

并查集

合并的优化:

查询的优化—路径压缩:

1 评论