UVA10054 The Necklace题解

Scorilon / 2023-08-30 / 原文

题意

给定一个无向图，其中至多有 \(50\) 个结点，求是否有欧拉回路。

题解

很明显就是一个无向图求欧拉回路的板子，我们用 \(\tt{Hierholzer}\)，先说存图，要明确的一个点是这个无向图里是有可能有重边的，所以我们要注意记录的时候不应是单独地记录某一条边是否存在，而是要记录某一条边的数量。这里用邻接矩阵来存图。然后在记录路径时要注意逆序输出，多测要记得清空。

在每完成一组数据时，要注意输出换行，其中最后一行不用，否则会 \(\tt{WA}\)，不要问我为什么，问就是被坑了很久。

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N=55;

int d[N],G[N][N];//d存度数，G存图

void dfs(int u) {//Hierholzer算法核心
	for(int i=1;i<=50;i++) {
		if(G[u][i]) {
			G[u][i]--;
			G[i][u]--;
			dfs(i);
			printf("%d %d\n",i,u);//逆序输出
		}
	}
}

int main() {
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++) {
		if(k>1) printf("\n"); //!!!
		int n;
		int s;
		scanf("%d",&n);
		int u,v;
		memset(d,0,sizeof(d));//多测清空
		memset(G,0,sizeof(G));
		for(int i=1;i<=n;i++) {
			scanf("%d%d",&u,&v);
			s=u;
			G[u][v]++;
			G[v][u]++;
			d[u]++;
			d[v]++;
		}
		int f=0;
		printf("Case #%d\n",k);
		for(int i=1;i<=50;i++) {
			if(d[i]&1) {//判断是否存在欧拉回路
				f=1;
				printf("some beads may be lost\n");
				break;
			}
		}
		if(f) continue;
		dfs(s);
	}
	return 0;
}