有n個珠子，每顆珠子有左右兩邊兩種顏色，顏色有1~50種，問你能不能把這些珠子按照相接的地方顏色相同串成一個環(huán)。

可以認為有50個點，用n條邊它們相連，問你能不能找出包含所有邊的歐拉回路

首先判斷是否在一個聯(lián)通分量中，在判斷是否存在歐拉回路，最后輸出歐拉回路。

1 #include <stdio.h> 2 #include <string.h> 3 const int maxn=55; 4 const int INF=1<<30; 5 int mx,mn,p[maxn],d[maxn],G[maxn][maxn]; 6 int find(int x) 7 { 8 return p[x]==x?x:(p[x]=find(p[x])); 9 } 10 void dfs(int u) 11 { 12 for(int v=mn;v<=mx;v++)if(G[u][v]){ 13 --G[u][v];--G[v][u]; 14 dfs(v); 15 printf("%d %d\n",v,u); 16 } 17 } 18 int main() 19 { 20 int t; 21 scanf("%d",&t); 22 for(int i=1;i<=t;i++){ 23 if(i!=1)putchar('\n'); 24 printf("Case #%d\n",i); 25 int j,n; 26 scanf("%d",&n); 27 for(j=1;j<=50;j++)p[j]=j; 28 memset(d,0,sizeof(d)); 29 memset(G,0,sizeof(G)); 30 int x,y; 31 mn=INF;mx=0; 32 for(j=1;j<=n;j++){ 33 scanf("%d%d",&x,&y); 34 ++G[x][y];++G[y][x]; 35 ++d[x];++d[y]; 36 if(mn>x)mn=x;if(mn>y)mn=y; 37 if(mx<x)mx=x;if(mx<y)mx=y; 38 x=find(x);y=find(y); 39 if(x!=y)p[x]=y; 40 } 41 int tmp=find(mn); 42 bool ok=1; 43 for(j=mn+1;j<=mx;j++)if(d[j] && find(j)!=tmp){ 44 ok=0;break; 45 } 46 if(ok) 47 for(j=mn;j<=mx;j++)if(d[j]&1){ 48 ok=0;break; 49 } 50 if(ok){ 51 dfs(mn); 52 }else{ 53 puts("some beads may be lost"); 54 } 55 } 56 return 0; 57 }

?

轉載于:https://www.cnblogs.com/acmicky/p/3351530.html

總結

以上是生活随笔為你收集整理的UVA 10054 the necklace 欧拉回路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。