10054 - The Necklace(欧拉回路+回路打印)

发布时间:2016-12-10 11:33:57 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"10054 - The Necklace(欧拉回路+回路打印)",主要涉及到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--){ //init memset(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]++; } //find int 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); else printf("some beads may be lost\n"); } if(t) printf("\n"); } return 0; }

上一篇:汇编习题
下一篇:C++基础学习系列-1-字符串的读取和显示

相关文章

相关评论