Written by razrlele
22:03 February 19, 2015
同欧拉系列。。。
不过这个应该是Eulerlan Cycle，然后只有两种情况：
1.可以拼回来，即成功构成Eulerlan Cycle。
2.少珠子，只能是个半环。
其他的情况都不用考虑。最后一个后续遍历打印就可以了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
/******************************************************** * File Name: uvaoj10054.cpp * Author: razrLeLe * Mail: razrlele@gmail.com * Homepage: https://yueyu.io * Created Time: Tue 17 Feb 2015 11:39:52 AM CST ******************************************************/ #include "vector" #include "set" #include "deque" #include "queue" #include "algorithm" #include "functional" #include "iostream" #include "cstdio" #include "cmath" #include "cstdlib" #include "string" #include "cstring" #include "string.h" #include "map" #include "cctype" #include "list" #include "stack" using namespace std; #define INF 0x3f3f3f3f #define LOCAL const int maxn = 55; int grid[maxn][maxn]; int cnt[maxn]; bool orderable; void Print(int a) { for(int i = 1; i <= 50; i++) { if(grid[a][i]) { grid[a][i]--; grid[i][a]--; Print(i); printf("%d %d\n", i, a); } } } int main() { #ifdef LOCAL freopen("/home/razrlele/build/data.txt", "r", stdin); freopen("/home/razrlele/build/out.txt", "w", stdout); #endif int numcase = 0; scanf("%d", &numcase); for(int nc = 1; nc <= numcase; nc++) { orderable = true; if(nc > 1) printf("\n"); printf("Case #%d\n", nc); memset(cnt, 0, sizeof(cnt)); memset(grid, 0, sizeof(grid)); int a, b, n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d %d", &a, &b); grid[a][b]++; grid[b][a]++; cnt[a]++; cnt[b]++; } for(int i = 1; i <= 50; i++) { if(cnt[i]%2) { orderable = false; break; } } if(orderable) { for(int i = 0; i <= 50; i++) { if(cnt[i]) { Print(i); break; } } } else printf("some beads may be lost\n"); } return 0; } |