基环树

基环树

题目传送门

题目大意:

给一个图,问该图是否是一颗基环树。

基环树:只有一个环并且连通的图

思路:

连通树满足边数等于点数减一

基环数满足边数等于点数

ll fa[N] ;

ll find(ll x){
	return fa[x] = fa[x] == x ? x : find(fa[x]) ;
}

string solve(){//基环树 
	cin >> n >> m ;
	if(n != m)return "NO\n" ;

	rep(i , 0 , n) fa[i] = i ;
	
	ll cnt = n ;
	rep(i , 1 , m){
		ll u , v ; cin >> u >> v ;
		
		ll fu = find(u) ;
		ll fv = find(v) ;
		
		if(fu != fv){
			cnt -- ;
			fa[fu] = fv ;
 		}	
	} 
	if(cnt == 1) return "YES\n" ;
	return "NO\n" ;
}
上一篇:2022牛客寒假算法基础集训营2


下一篇:AcWing 1996. 打乱字母(贪心+二分)