题目描述
判断一个无向图是否联通
算法
并查集
可以直接用并查集判断所有点是否都处在同一个集合内
不知道并查集是什么的可以去看算法基础课(
时间复杂度
nlogn
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n,m;
int fa[N];
int find(int x){
if(x!=fa[x])fa[x]=find(fa[x]);
return fa[x];
}
void merge(int a,int b){
fa[find(a)]=find(b);
}
int main(){
while(cin>>n>>m){
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1,a,b;i<=m;i++){
cin>>a>>b;
merge(a,b);
}
bool flag=1;
for(int i=1;i<=n;i++){
if(find(i)!=find(1)){
flag=0;
break;
}
}
if(flag)puts("YES");
else puts("NO");
}
return 0;
}