UVA10054 The Necklace

 1 #include<cstdio>
 2 #include<queue>
 3 #include<vector>
 4 #include<cstring>
 5 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
 6 using namespace std;
 7 
 8 const int maxn = 50+10;
 9 const int N=50;
10 struct Node{
11     int u,v;
12 };
13 int n,m;
14 int deg[maxn],G[maxn][maxn];
15 
16 vector<Node> ans;
17 void euler(int u) {
18     FOR(v,1,N) if(G[u][v]) {
19               G[u][v]--; G[v][u]--;
20               euler(v);
21               ans.push_back((Node){u,v});
22        }
23 }
24 
25 int main() {
26     int T,kase=0;
27     scanf("%d",&T);
28     while(T--)
29     {
30         memset(deg,0,sizeof(deg));
31         memset(G,0,sizeof(G));
32         scanf("%d",&n);
33         int u,v,start=-1;
34         FOR(i,1,n) {
35             scanf("%d%d",&u,&v);
36             G[u][v]++; G[v][u]++;
37             deg[u]++; deg[v]++;
38             start=u;
39         }
40         bool solved=true;
41         FOR(i,1,N)  if(deg[i]&1) { solved=false; break; }
42         if(solved) {
43             ans.clear();
44             euler(start);
45             if(ans.size()!=n || ans[0].v!=ans[ans.size()-1].u) solved=false;  //注意ans是逆序 
46         }
47         printf("Case #%d\n",++kase);
48         if(!solved) printf("some beads may be lost\n");
49         else
50            for(int i=ans.size()-1;i>=0;i--) printf("%d %d\n",ans[i].u,ans[i].v);
51         if(T) putchar(‘\n‘);
52     }
53     return 0;
54 }