题解 ABC231D【Neighbors】

首先，每个数不能有超过两个相邻元素，不然无法构成一条链。可以通过记录每个数出现次数（度数）来判断。

其次，给的信息不能成环，不然也无法构成一条链。可以通过并查集来判断。

在以上两个判断之后，剩余的情况一定有解，可以通过不断找度数小于 \(2\) 的点作为起点，依次通过若干度数等于 \(2\) 的点，最终停留在度数小于 \(2\) 的点作为终点，重复若干次得到。

时间复杂度 \(\Theta(n\alpha(n))\)。

// Problem: D - Neighbors
// Contest: AtCoder - Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)
// URL: https://atcoder.jp/contests/abc231/tasks/abc231_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e5+5;

int n, m, deg[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Dsu {
	int fa[N], rk[N];
	void init(int x) {rep(i, 1, x) fa[i] = i, rk[i] = 0;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	bool merge(int x, int y) {
		int u = find(x), v = find(y);
		if(u == v) return 0;
		if(rk[u] < rk[v]) swap(u, v);
		chkmax(rk[u], rk[v] + 1);
		fa[v] = u;
		return 1;
	}
}dsu;

int main() {
	scanf("%d%d", &n, &m);
	dsu.init(n);
	rep(i, 1, m) {
		int u, v;
		scanf("%d%d", &u, &v);
		++deg[u]; ++deg[v];
		if(!dsu.merge(u, v)) return puts("No")&0;
	}
	if(*max_element(deg+1, deg+1+n) > 2) puts("No");
	else puts("Yes");
	return 0;
}