題目：
My little sister had a beautiful necklace made of colorful beads. Two successive beads in the necklace shared a common color at their meeting point. The figure below shows a segment of the necklace:
But, alas! One day, the necklace was torn and the beads were all scattered over the floor. My sister did her best to recollect all the beads from the floor, but she is not sure whether she was able to collect all of them. Now, she has come to me for help. She wants to know whether it is possible to make a necklace using all the beads she has in the same way her original necklace was made and if so in which order the bids must be put.
Please help me write a program to solve the problem.
題目大意翻譯：
我的妹妹有一串由各種顏色組成的項鏈。 項鏈中兩個連續珠子的接頭處共享同一個顏色。 如上圖， 第一個珠子是green+red, 那麼接這個珠子的必須以red開頭，如圖的red+white.
噢！天啊！ 一天， 項鏈項鏈被扯斷了，珠子掉落了一地。我的妹妹竭盡全力的把珠子一個個撿起來， 但是她不確定是否全部撿回來了。 現在，她叫我幫忙。
她想知道是否可能把這些珠子全部連接起來， 連接的方法和項鏈原來的方法一樣。
請幫我寫一個程序解決這個問題。
樣例輸入：
2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4
樣例輸出：
Case #1
some beads may be lost
Case #2
2 1
1 3
3 4
4 2
2 2
思路與總結：
這題就是歐拉回路+打印路徑，
和UVa 10129 - Play on Words, 歐拉道路 這題很像，
有所不同的是，那題是有向圖，而這一題是無向圖， 那一題是求歐拉道路，而這一題求的是歐拉回路。
歐拉道路和歐拉回路的區別是， 歐拉回路是要從某一點出發，最後又回到這一點，形成回路。而歐拉道路是從一點出發，到另一個點結束。
打印歐拉回路的方法， 劉汝佳《算法入門經典》P112上有詳細介紹：
下面是的遞歸函數同時適用於歐拉道路和回路。如果需要打印的是歐拉道路，在主程序調用時，參數必須是道路的起點。另外，打印的順序是你序的，因此真正使用這份
代碼時，應當把printf語句替換成一條push語句，把邊壓入一個棧內。
[cpp]
void euler(int u){
for(int v=0; v<MAXN; ++v) if(G[u][v]){
vis[u][v] = vis[v][u] = 1;
euler(v);
printf("%d %d\n", u,v);
}
}
上代碼使用於無向圖， 如果改成有向圖，把vis[u][v] = vis[v][u] = 1改成vis[u][v]= 1即可。
在這一題中， 由於可能會出現重復的，比如：
1 2
2 2
2 2
2 2
2 3
3 1
1 2
2 1
所以需要稍微改變一下
[cpp]
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#define MAXN 60
using namespace std;
int vis[MAXN],cnt[MAXN],G[MAXN][MAXN],T, vis2[MAXN][MAXN], N, a, b;
struct Node {int u,v; };
stack<Node>st;
void dfs(int u){
vis[u] = true;
for(int i=0; i<MAXN; ++i){
if(G[u][i] && !vis[i])
dfs(i);
}
}
void euler(int u){
for(int v=0; v<MAXN; ++v) if(G[u][v]){
--G[u][v]; --G[v][u];
euler(v);
Node t;
t.u = u, t.v = v;
// st.push(t);
printf("%d %d\n", u,v);
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int cas=1;
scanf("%d",&T);
while(T--){
memset(G, 0, sizeof(G));
memset(cnt, 0, sizeof(cnt));
scanf("%d",&N);
for(int i=0; i<N; ++i){
scanf("%d %d",&a,&b);
++G[a][b];
++G[b][a];
++cnt[a];
++cnt[b];
}
bool flag=true;
for(int i=0; i<MAXN; ++i){
if(cnt[i] & 1){ flag=false; break;}
}
printf("Case #%d\n",cas++);
if(flag){
memset(vis, 0, sizeof(vis));
memset(vis2, 0, sizeof(vis2));
int flag2=true;
for(int i=0; i<MAXN; ++i)
if(cnt[i]) { dfs(i); break; }
for(int i=0; i<MAXN; ++i){
if(cnt[i] && !vis[i]) {flag2=false; break;}
}
if(flag2){
for(int i=0; i<MAXN; ++i) if(cnt[i]){
euler(i);
break;
}
// 這裡可以遞歸時直接逆向打印，也可存到棧裡在打印出來
// while(!st.empty()){
// printf("%d %d\n", st.top().u, st.top().v);
// st.pop();
// }
}
else printf("some beads may be lost\n");
}
else{
printf("some beads may be lost\n");
}
if(T) printf("\n");
}
return 0;
}
作者：shuangde800
