搜索技术|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; }

    推荐阅读