ABC-404-C - Cycle Graph? · znzryb

## 思路讲解

只要大家入度都为2就行了。

但是注意，上面这句话成立的条件是在联通图下。

## AC代码

[https://atcoder.jp/contests/abc404/submissions/65464102](https://atcoder.jp/contests/abc404/submissions/65464102)



::: 源代码

```cpp
// Problem: C - Cycle Graph?
// Contest: AtCoder - AtCoder Beginner Contest 404
// URL: https://atcoder.jp/contests/abc404/tasks/abc404_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T;
vector<ll> g[MAXN];
struct DSU {  // refer jiangly
  vector<int> fa, siz;
  int ln;
  DSU(int n) {
    ln = n;
    fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
    FOR(i, 1, n) {
      fa[i] = i;
      siz[i] = 1;
    }
  }
  int find(int x) {
    while (fa[x] != x) {
      x = fa[x];
      fa[x] = fa[fa[x]];
    }
    return x;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    siz[x] += siz[y];
    fa[y] = x;
    return true;
  }
  int size(int x) { return siz[find(x)]; }
  int countFa() {
    int res = 0;
    FOR(i, 1, ln) {
      if (fa[i] == i) ++res;
    }
    return res;
  }
};

inline void solve(){
	cin>>N>>M;
	// vector<arr> ls;
	DSU dsu(N);
	FOR(i,1,M){
		ll u,v;
		cin>>u>>v;
		if(u>v) swap(u,v);
		g[u].pb(v);
		g[v].pb(u);
		dsu.merge(u,v);
	}
	if(dsu.countFa()!=1){
		cout<<"No\n";
		return;
	}
	if(M==N){
		// sort(all(ls));
		// if(ls[0][0]==1 && ls[0][1]==2){
			// if(ls[1][0]==1 && ls[1][1]==N){
				// FOR(i,2,SZ(ls)-2){
					// if(ls[i][0]==i && ls[i][1]==i+1){
// 						
					// }else{
						// cout<<"No\n";
						// return;
					// }
				// }
				// cout<<"Yes\n";
				// return;
			// }
		// }
		FOR(i,1,N){
			if(SZ(g[i])!=2){
				cout<<"No\n";
				return;
			}
		}
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/
```


:::


## 心路历程（WA，TLE，MLE……）