10054 - The Necklace（欧拉回路+回路打印）

本文主要是介绍10054 - The Necklace（欧拉回路+回路打印），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：10054 - The Necklace

题目大意：给出N给珠子，每个珠子都有两种颜色，各半，看能不能找出每种组合使珠子连成一串，颜色相同的珠子才能相邻。

解题思路：欧拉回路+ 回路打印。

刚开始的时候我直接以珠子的个数来考虑是否有欧拉回路，这样的话1000*1000 *1000...次判断导致超时了。这里可以判断颜色，颜色都访问过了，就说明这串珠子是连通的。然后要输出的时候就在按照珠子的个数来考虑。

#include<stdio.h>
#include<string.h>const int N = 55;
int t, n, map[N][N], v[N], ino[N];void dfs(int x, int &m) {v[x] = 1;m++;for(int  i = 1; i <= 50; i++)if(map[x][i] && !v[i]) dfs(i, m);}void printff(int x) {for(int i = 1; i <= 50; i++)if(map[x][i]) {map[x][i]--;map[i][x]--;printff(i);printf("%d %d\n", i, x);}}int color_num () {int num = 0;for(int i = 1 ; i <= 50; i++)if(ino[i])num++;return num;			
}int main() {scanf("%d", &t);int num = t;while(t--){//initmemset(map, 0, sizeof(map));memset(v, 0, sizeof(v));memset(ino, 0, sizeof(ino));scanf("%d", &n);int i, x, y;for(i = 1; i <= n; i++) {scanf("%d%d", &x, &y);map[x][y] ++;map[y][x] ++;ino[y]++;ino[x]++;}//findint ok = 0;for(i = 1; i <= 50; i++) if(ino[i] % 2) {ok = -1;break;}printf("Case #%d\n", num - t);if(ok == -1)printf("some beads may be lost\n");else {dfs(x, ok);if(ok == color_num())printff(x);elseprintf("some beads may be lost\n");}if(t)printf("\n");}return 0;
}

这篇关于10054 - The Necklace（欧拉回路+回路打印）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---