无向图找环。我这种方法貌似比普通方法快一点也简洁点,有没有dalao求一下时间复杂度?
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,fa[1000000+10];
ll fin(ll x){
if(fa[x]==x) return x;
else return fa[x]=fin(fa[x]);
}
int main(){
cin>>n>>m;
for(ll i=1;i<=m;i++){
ll x,y;
cin>>x>>y;
if(fa[x]==0) fa[x]=x;
if(fa[y]==0) fa[y]=y;
ll t1=fin(x),t2=fin(y);
if(t1==t2){
cout<<"Yes";
return 0;
}
fa[t1]=t2;
}
cout<<"No";
return 0;
}