首页 > 代码库 > UVA 10054 (欧拉回路) The Necklace
UVA 10054 (欧拉回路) The Necklace
题目：这里
题意：有一种由彩色珠子连接而成的项链，每个珠子两半由不同颜色(由1到50的数字表示颜色)组成，相邻的两个珠子在接触的地方颜色相同，现在有一些零碎的珠子，确认它是否能
复原成完整的项链。
把每种颜色看成一个结点，每个珠子的两半连成一条有向边，就成了判断一个欧拉回路了，而输出回路路线可以用dfs，逆序输出，因为顺序输出的时候，由于可能会有一个结点上多
条边的情况，dfs的时候可能一开始会找到错误的路线再回溯回去，顺序输出就把这段错误的路线也输出了。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 8 const int M = 1e3 + 10; 9 int cas,head[M*4],father[60],du[60];10 int vis[60][60];11 12 struct Edge{13 int next,to;14 }edge[M*4];15 16 int findest(int x)17 {18 if (x==father[x]) return x;19 father[x]=findest(father[x]);20 return father[x];21 }22 23 void add(int v,int u)24 {25 edge[++cas].next=head[v];26 edge[cas].to=u;27 head[v]=cas;28 }29 30 void euler(int u)31 {32 for (int i=head[u] ; i ; i=edge[i].next){33 int v=edge[i].to;34 if (!vis[u][v]) continue;35 vis[u][v]--;vis[v][u]--;36 euler(edge[i].to);37 printf("%d %d\n",v,u);38 }39 }40 41 int main()42 {43 int t,tem=0;44 scanf("%d",&t);45 int e=t;46 while (t--)47 {48 int n,w;cas=0;49 scanf("%d",&n);50 memset(du,0,sizeof(du));51 memset(vis,0,sizeof(vis));52 memset(head,0,sizeof(head));53 for (int i=1 ; i<=50 ; i++) father[i]=i;54 for (int i=1 ; i<=n ; i++) {55 int l,r;56 scanf("%d%d",&l,&r);57 if (i==1) w=l;58 du[l]++;du[r]++;59 add(l,r);60 add(r,l);61 vis[l][r]++;vis[r][l]++;62 int x=findest(l),y=findest(r);63 if (x!=y) father[x]=y;64 }65 bool flag=false;66 int x=findest(w);67 for (int i=1 ; i<=50 ; i++){68 if (du[i]==0) continue;69 if (du[i]%2!=0) flag=true;70 if (findest(i)!=x) flag=true;71 if (flag) break;72 }73 cas=0;74 if (tem!=0) printf("\n");75 printf("Case #%d\n",++tem);76 if (flag) puts("some beads may be lost");77 else euler(w);78 }79 return 0;80 }
UVA 10054 (欧拉回路) The Necklace
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。