UVA10054 The Necklace——欧拉回路（DFS）

点这里

---

题意： 有n个珠子。每个珠子有两种颜色，分布在珠子的两边。一共有50种不同的颜色。把这些珠子串起来，要求两个相邻的珠子接触的部分颜色相同。问是否能连成一个珠串项链？如果能，打印出一种连法。
题解： 一开始看样例其实我有点懵 ，每行给出某个珠子的两个颜色，然后相同颜色的能相连。其实我们换个角度，把行输入看成是一条边（原本代表一个珠子的两个颜色），把每种颜色看成一个点。那么我们的任务就简单明了了，把所有的颜色连起来，每条边通过且只通过一次——欧拉回路。

• 连通。 一般情况下是需要用DFS、并查集等方法来判断图的连通性的，但是这道题比较简单，用不上；给出的图都是能够连通的。
• 判断欧拉回路。 首先明确这是一个无向连通图，而无向连通图中欧拉回路的判断条件就是图中的点全都是偶点。
• 输出欧拉回路。 用DFS即可。但注意程序中递归要在输出之前！

---

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;

int T, cnt, n, a, b;
int deg[N], G[N][N];
bool check(){	for(int i = 1; i <= 50; i++)	if(deg[i] % 2)	return false;	return true;}
void euler(int u){
	for(int v = 1; v <= 50; v++){
		if(G[u][v]){
			G[u][v]--, G[v][u]--;
			euler(v);			／／先递归再输出
			printf("%d %d\n", v, u);
		}
	}
}
int main(){
	scanf("%d", &T);while(T--){
		memset(deg, 0, sizeof deg);
		memset(G, 0, sizeof G);
		scanf("%d", &n);
		for(int i = 0; i < n; i++){
			scanf("%d%d", &a, &b);
			deg[a]++, deg[b]++;
			G[a][b]++, G[b][a]++;
		}
		printf("Case #%d\n", ++cnt);
		if(!check()) printf("some beads may be lost\n");
		else	euler(b);
		puts("");
	}
	return 0;
} 

本文地址：https://blog.csdn.net/m0_46187157/article/details/108184606