Codeup 并查集之问题 A: 通信系统

柔情只为你懂 2023-02-14 02:11 8阅读 0赞

#### 思路： ####

利用并查集建立起端点与端点的关系  
题目要求：  
**1.某个端点生成后，其余各个端点均能接收到消息**  
这句话转换到并查集的思想就是所有的端点应该在一个集合之中，如果存在多个集合，因为集合和集合之间并没有数据链路连通，所以无法传递消息

**2.并且每个端点均不会重复收到消息**  
这其实就是合并集合的时候，当判断两个结点的根结点为相同时，意味着两个端点之间存在两条链路，构成一个环，只需要记录一下环的数量最后判别即可  
写的时候注意路径压缩，亲测路径压缩后时间复杂度下降为原来的十分之一

#include<iostream>
    using namespace std;
    int father[1010];
    bool isroot[1010];
    int cnt=0;//环数 
    //判断集合个数，为1并且不存在环输出yes
    int findfather(int a)
    { 
        int c=a;
        while(father[a]!=a)
        { 
            a=father[a];
        }
        //路径上的每个结点直接指向根结点，压缩路径
        while(father[c]!=c)
        { 
        	int b=c;
        	c=father[c];
        	father[b]=a;
        } 
        return a;
    }
    void Union(int a,int b)//合并集合
    { 
        int faa=findfather(a);
        int fab=findfather(b);
        if(faa!=fab)
        { 
            father[faa]=fab;
        }
        else
    	cnt++; 
    }
    void init()//初始化
    { 
        for(int i=0;i<1010;i++)
        { 
            father[i]=i;
            isroot[i]=false;
        }
        cnt=0;
    }
    int main()
    { 
        
        int n,m;
        while(cin>>n>>m)
        { 
            if(n==0&&m==0)break;
            init();  
            int a,b;
            for(int i=0;i<m;i++)
            { 
                cin>>a>>b;
                Union(a,b);
            }
            for(int i=1;i<=n;i++)//根结点标记为true 
            { 
                isroot[findfather(i)]=true;
            }
            int ans=0;
            bool flag1=true;
            for(int i=1;i<=n;i++)
            { 
                if(isroot[i])ans++;
                if(ans>1)
                { 
                    flag1=false;
                    break;
                }
            }
            if(flag1&&cnt==0)cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        return 0;
    }