題目意思：有一堆散落的項鏈的的珠子，珠子有可能重復的出現，問我們能否連接成一條項鏈，要求該項鏈的每一節的兩個珠子要滿足，“第一個珠子必須和前一節的第二個珠子相同，對於最後一節的第二個珠子必須和第一節的第一個相同“。問能否實現，如果可以輸出其中一種路徑
解題思路：題目意思是判斷是否可以連乘一個環，滿足歐拉回路的條件，那麼題目就轉化為給個一個歐拉路判斷是否是連通。我們知道對於判斷歐拉道路是否是連通的我們都是采用建立一個無向圖的鄰階矩陣，然後輸出操作
第一步：任何一條歐拉回路滿足所有的度數和為偶數，那麼先判斷是否滿足該條件，不滿足直接退出
第二步：我麼在鄰階矩陣map中找到一個有出度的點進行路徑搜索 ， 對於路徑的輸出，我們一般用遞歸，利用棧來存儲節點的坐標，最後逆序輸出。
代碼：
[cpp]
//對於項鏈是否可以滿足索給的條件，那麼我們先判斷輸入的數據是否是歐拉回路，即度數的和是否全部為偶數，如果是我們再去打印出一條路徑
#include <iostream>
#include <cstdio>
#include <cctype>
#include <stack>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAXN = 60;
//結構體存儲兩個對應的坐標
struct node{
int x;
int y;
};
node p;
int t , n;
int map[MAXN][MAXN];//無向圖的鄰階矩陣（搜索路徑或判斷連通都要用無向圖的鄰階矩陣）
int eur[MAXN];//存儲每個節點的度數
int flag;
stack<node>s;//棧用來存儲節點的坐標
//
inline void output(int u){
for(int i = 0 ; i <= 50 ; i++){
if(map[u][i]){
--map[u][i];//相應點減1
--map[i][u];
output(i);//繼續向下搜索
node temp;
temp.x = u ; temp.y = i;
s.push(temp);//把點壓入棧中（逆序輸出）
}
}
}
//
inline void solve(){
int i , j , temp;
temp = 0;
for(i = 1 ; i <= 50 ; i++){
for(j = 1; j <= 50 ; j++){
if(map[i][j]){
output(i);//找到有出度的點開始搜索路徑
temp = 1;
break;//直接跳出
}
}
if(temp)
break;//直接跳出
}
while(!s.empty()){//輸出結果
node temp = s.top();
printf("%d %d\n" , temp.x , temp.y);
s.pop();
}
}
//
int main(){
int i , k;
int x , y;
scanf("%d" , &t);
for(k = 1 ; k <= t ; k++){
scanf("%d" , &n);
flag = 1;
memset(map , 0 , sizeof(map));
memset(eur , 0 , sizeof(eur));
for(i = 0 ; i < n ; i++){
scanf("%d%d" , &x , &y);
map[x][y]++;//鄰階矩陣的建立
map[y][x]++;
eur[x]++;//度數加1
eur[y]++;
}
for(i = 0 ; i <= 50 ; i++){//判斷滿足歐拉回路
if(eur[i] %2 != 0){
flag = 0;
break;
}
}
printf("Case #%d\n" , k); www.2cto.com
if(flag == 0)//不滿足歐拉回路直接輸出
printf("some beads may be lost\n");
else
solve();
if(k != t)
printf("\n");//最後沒有空行
}
return 0;
}
