帮我看看这个想法对不对?
  • 板块灌水区
  • 楼主ZSYhaouuan
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/11/11 21:16
  • 上次更新2024/11/12 09:20:56
查看原帖
帮我看看这个想法对不对?
1385996
ZSYhaouuan楼主2024/11/11 21:16

无向图找环。我这种方法貌似比普通方法快一点也简洁点,有没有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;
}

2024/11/11 21:16
加载中...