题目：The Necklace
思路：
把颜色看做点，珠子看做边，找欧拉回路。
注意：
判断是否为欧拉图时要判断图的联通性。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 1000
#define n 50 //点 int m; //边int g[n+5][n+5]; //邻接矩阵
int cnt[n+5]; //记录点的度 bool a[n+5]; //点是否在图中 int k; //某一个在图中的点 void init() { //初始化 memset(g,0,sizeof(g));memset(cnt,0,sizeof(cnt));memset(a,0,sizeof(a));
}void readin() { //读入 scanf("%d",&m);for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);g[x][y]++,g[y][x]++;cnt[x]++,cnt[y]++;}
}int rch(int k) { //判断图的连通性 a[k]=true;int s=1;for(int i=1; i<=n; i++) {if(g[i][k]&&!a[i]) {s+=rch(i);}}return s;
}bool judge() { //判断是否为欧拉图 for(int i=1; i<=n; i++) {if(cnt[i]&1) return false;}int s=0;for(int i=1; i<=n; i++) {if(cnt[i]) {s++;k=i;}}if(rch(k)!=s) return false;return true;
}void dfs(int x) { //输出 for(int i=1; i<=n; i++) {if(g[x][i]) {g[x][i]--,g[i][x]--;dfs(i);printf("%d %d\n",i,x);}}
}int main() {int T,t=0;scanf("%d",&T);while(T--) {init();readin();if(judge()) {printf("Case #%d\n",++t);dfs(k);} else {printf("Case #%d\nsome beads may be lost\n",++t);}if(T) printf("\n");}return 0;
}