题目大意：有一堆珠子，每颗珠子的两端分别有两种颜色，现在要将这些珠子串成一串，要求相邻的两颗珠子接触的一端颜色需要相同，问是否能串成一串，若能串成一串，给出这些的珠子连接顺序。
想法：这是一题图论中欧拉回路的题。将每一个珠子视作一条边，每种颜色作为点，判断这图是否构成欧拉回路。先判断该图是否连通，可以用并查集做；然后判断每个点的度，若每个点的度都是偶数，可以构成欧拉回路，若只有两个奇数度的点，可以构成欧拉路径。这题需要是欧拉回路，相对简单一点。判断出是欧拉回路之后，找出一条欧拉路径，具体看http://www.doc88.com/p-213653234247.html，上面写得很详细。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; int a[52][52],x[1012],y[1012],p[52],f[52]; int m,loc,cir,sum,num,z,p1; void clear1() { int i; memset(p,0,sizeof(p)); memset(a,0,sizeof(a)); for (i=1;i<=50;i++) f[i]=i; } int find(int x) { if (f[x]!=x) f[x]=find(f[x]); return f[x]; } int main() { int T,i,faz; stack<int>st; scanf("%d",&T); for (int I=1;I<=T;I++) { clear1(); scanf("%d",&m); for (i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); int fx=find(x[i]),fy=find(y[i]); if (fx!=fy) f[fy]=fx; a[x[i]][y[i]]++; a[y[i]][x[i]]++; p[x[i]]++; p[y[i]]++; } faz=find(x[1]); for (i=1;i<=m;i++) { if (find(x[i])!=faz||find(y[i])!=faz) { faz=0; break; } } printf("Case #%d\n",I); if (faz==0) printf("some beads may be lost\n"); else { sum = 0; for (i=1;i<=50;i++) if (p[i] % 2==1) sum++; if (sum==0) { i=1; while (p[i]==0) i++; loc=i; num=0; cir=0; while (num<m) { p1=0; while (!p1) { for (i=1;i<=50;i++) if (a[loc][i]>0) { st.push(loc); a[loc][i]--; a[i][loc]--; loc=i; p1=1; break; } if (!p1) { if (cir!=0) printf("%d %d\n",cir,loc); cir = loc; loc=st.top(); st.pop(); } } num++; } while (!st.empty()) { if (cir!=0) printf("%d %d\n",cir,loc); cir = loc; loc=st.top(); st.pop(); } printf("%d %d\n",cir,loc); } else printf("some beads may be lost\n"); } if (I<T) printf("\n"); } return 0; }