[普及/提高-]A106404.

题意（形式化）

一个无向图有 $n$ 个顶点和 $m$ 条边，问能不能将这个无向图摊开在一个链表上。

思路

快速略过。

有两种情况不可行，其余情况可行：

1. 当一个点的度大于 $2$，显然，一个链表的出度只是其左边和右边两个度，当一个点有 $3$ 个及以上的度时将无任何方法使其成为邻居。
2. 当出现环时，链表不可能有环，无法使其全部成为邻居。

实现可以通过并查集判环，维护一个数组存一个节点的度。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 2 * 1e5 + 5;
int fa[N] , n , size[N] , m , in[N];
void into(int n){
	for(int i = 1;i <= n;i ++){
		fa[i] = i;
		size[i] = 1;
	}
}
int Find(int x){
	if(x == fa[x]){
		return x;
	}
	return fa[x] = Find(fa[x]);
}
void Union(int x , int y){
	int rx = Find(x) , ry = Find(y);
	if(rx == ry){
		return; 
	}
	if(size[ry] > size[rx]){
		swap(rx , ry);
	}
	fa[ry] = rx;
	size[rx] += size[ry];
	return;
}
signed main(){
	cin >> n >> m;
	into(n);
	for(int i = 1;i <= m;i ++){
		int a , b;
		cin >> a >> b;
		in[a] ++;
		in[b] ++;
		if(in[a] > 2 || in[b] > 2){
			cout << "No" << endl;
			return 0;
		}
		if(Find(a) == Find(b)){
			cout << "No" << endl;
			return 0;
		}
		Union(a , b);
	}
	cout << "Yes" << endl;
	return 0;
}