判断无向图是否存在欧拉回路/欧拉通路的模板---使用并查集判断是否连通

7-18 一笔画 (45分)

小丁最近迷恋上一个游戏，传说中的“一笔画”游戏。

那么什么是一笔画？如下图，顾名思义就是一笔可以完成的图。一笔画最基本的要求是在画图的过程中，笔不能离开纸，且笔所画过的线不能重复，最后画完所有的线便算完成。

虽然小丁喜欢玩这个游戏，但有时候花费半天也找不到答案。小丁听说写一个计算机程序便能判断是否可以一笔画图，所以他希望善良可爱的你来帮帮他的忙。

快来帮帮弱小，可怜，又无助的小丁。

输入格式:

给出图中的节点数N（1<=N<=1000,编号1-N）和边数M；随后M行给出存在边的两个节点的编号。

输出格式:

能够一笔画的图输出Y，否则输出N。

输入样例1:

3 2
1 2
2 3

输出样例1:

Y

输入样例2:

4 3
1 2
1 3
1 4

输出样例2:

N

对于无向图

欧拉通路:图连通；图中只有2个度为奇数的节点(就是欧拉通路的2个端点)

欧拉回路:图连通；图中无奇度顶点

#include <cstdio>
using namespace std;
const int maxn = 1010;
int n, m; //节点数 和 边数 
int degree[maxn];
int fa[maxn]; //为并查集服务 

void init() { //初始化
	for(int i = 1; i <= n; i++) fa[i] = i;
}

int find_set(int x) { //查找---进行非递归路径压缩优化处理 
	int fa_x = x;
	while (fa[fa_x] != fa_x) fa_x = fa[fa_x]; //找到根结点
	
	int i = x, temp;
	while (i != fa_x) {
		temp = fa[i]; //用临时变量temp记录
		fa[i] = fa_x; //把路径上元素的集改为根结点
		i = temp;
	}
	
	return fa_x;
}

void union_set(int x, int y) { //合并
	int fa_x = find_set(x);
	int fa_y = find_set(y);
	//if (fa_x != fa_y) fa[fa_y] = fa_x; //向左合并
	if (fa_x != fa_y) fa[fa_x] = fa_y; //向右合并
}

int main()
{
	scanf("%d %d",&n,&m);
	init();
	int t1, t2;
	for(int i = 1; i <= m; i++) {
		scanf("%d %d",&t1,&t2);
		degree[t1]++;
		degree[t2]++;
		union_set(t1, t2);
	}
	
	/*判断是否为欧拉回路
	int flag = 1;
	for(int i = 1; i<= n; i++) {
		if (degree[i] % 2 != 0 || fa[i] != fa[1]) {
			flag = 0;
			break;
		}
	}
	
	if (flag) cout << "Y" << endl;
	else cout << "N" << endl;*/ 

	/*判断是否有欧拉通路(有欧拉回路必有欧拉通路) */ 
	int cnt = 0;
	int flag = 1;
	for(int i = 1; i <= n; i++) {
		if (degree[i] % 2 == 1) { //奇度顶点
			cnt++;
		}
		if (find_set(i) != find_set(1)) { //进去了说明不连通
			flag = 0;
			break;
		}
	}
	
	if ((cnt == 2 || cnt == 0) && flag) printf("Y\n");
	else printf("N\n");

	return 0;
}