搜索技术|UVA10054 The Necklace——欧拉回路（DFS） #|欧拉路|刷题

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

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

#include #include 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; }