<< 点个赞吧

$\ \ $

$\huge\color{Gold}{暑假每日一题2022}\color{black}{题解集合}$

$\ \ $

算法标签

${带边权并查集}$

分析

其实这题提到相连，就可以想到并查集

如果输入的 $x$ , $y$ 不相等的话就把它们所在的集合合并

最后判断最大的一个集合的边数是不是等于 $n$

C++ 代码

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
int f[121221],d[121212];
int n,m;
int get(int x){
    if(x==f[x]) return x;
    return f[x]=get(f[x]);
}
void merge(int x,int y){
    int a=get(x),b=get(y);
    if(a!=b) f[a]=b,d[b]+=d[a];

}
int main(){
    while(cin>>n>>m){
        for(int i=1;i<=n;i++) f[i]=i,d[i]=1;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            merge(x,y);
        }
        if(d[get(1)]==n) puts("YES");
        else puts("NO");
    }
    return 0;
}