http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=995
题目大意:
有一种由彩色珠子组成的项链,每个珠子的两半由不同的颜色组成,相邻的两个珠子在接触的地方颜色相同。现在有一些零碎的珠子,需要你确认是否可以复原,并且输出其中一种复原方案。
思路:
第一道欧拉回路的题。
思路很巧妙,把每个珠子的颜色看成点(注意是颜色!)而珠子则看成连接这两个点的边。
那么就转化为求欧拉回路了~
#include<cstdio> #include<cstring> #include<vector> using namespace std; const int MAXN=52; int map[MAXN][MAXN],d[MAXN]; struct edge { int from,to; edge(int from,int to): from(from),to(to){} }; vector <edge> ans; void euler(int cur) { for(int i=1;i<MAXN;i++) { if(map[cur][i]) { map[cur][i]--; map[i][cur]--; euler(i); ans.push_back(edge(cur,i)); } } } int main() { int T; scanf("%d",&T); for(int ri=1;ri<=T;ri++) { memset(map,0,sizeof(map)); memset(d,0,sizeof(d)); int n,start; scanf("%d",&n); for(int i=1;i<=n;i++) { int c1,c2; scanf("%d%d",&c1,&c2); map[c1][c2]++; map[c2][c1]++; d[c1]++; d[c2]++; start=c1; } bool ok=true; for(int i=1;i<MAXN;i++) { if(d[i] & 1){// 无向图为欧拉图的充要条件是没有度为奇数的顶点。 ok=false; break; } } if(ok) { ans.clear(); euler(start); if(ans.size()!=n || ans[0].to!=ans[n-1].from) ok=false; } if(ri!=1) printf("\n"); printf("Case #%d\n", ri); if(!ok) printf("some beads may be lost\n"); else { for(int i=n-1;i>=0;i--) printf("%d %d\n", ans[i].from, ans[i].to); } } return 0; }