[NJUPSOJ]Euler图

discription:
判断一个图是否为欧拉图(图本身是欧拉闭迹)
欧拉闭迹的定义:含有图中每一条边的闭合迹(trail).
迹(trail)的定义:一条没有重复边的途径(walk)
途径(walk)的定义:形如{\(x_0,x_1\)},{\(x_1,x_2\)},{\(x_2,x_3\)},...,{\(x_{n-1}, x_n\)}的边序列
闭合指\(x_0=x_n\)
定理:
一个图存在欧拉闭迹\(\Leftrightarrow\)存在连通分量每个点为even度数.
存在欧拉开迹\(\Leftrightarrow\)存在连通分量, 有且仅有2点为odd度数.
solution:
并查集维护图的连通性, 统计图的每个点度的奇偶性.
code:

#include<cstdio>
bool deg[2001];
int f[2001];
inline int find(const int& x) {
	if (f[x] == x)return x;
	return f[x] = find(f[x]);
}
inline void Union(const int &x, const int& y) {
	int fx = find(x), fy = find(y);
	if (fx < fy)f[fy] = fx;
	else f[fx] = fy;
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)f[i] = i;
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		deg[u]=!deg[u], deg[v]=!deg[v];
		Union(u, v);
	}
	for (int i = 1; i <= n; ++i) {
		if (deg[i] || find(i)!=1) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
}

[NJUPSOJ]Euler图

原文：https://www.cnblogs.com/dwt2021/p/14404147.html