大家好，又见面了，我是全栈君。
题目大意：我的妹妹有一串由各种颜色组成的项链。 项链中两个连续珠子的接头处共享同一个颜色。 如上图， 第一个珠子是green+red, 那么接这个珠子的必须以red开头，如图的red+white.
噢！天啊！ 一天， 项链项链被扯断了，珠子掉落了一地。我的妹妹竭尽全力的把珠子一个个捡起来， 但是她不确定是否全部捡回来了。 现在，她叫我帮忙。
她想知道是否可能把这些珠子全部连接起来， 连接的方法和项链原来的方法一样。
请帮我写一个程序解决这个问题。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=60; int n; int T,kase=0; int p[N]; int Find(int x) { if(p[x]==-1) return x; return x==p[x]? x:p[x]=Find(p[x]); } void Union(int x,int y) { x=Find(x),y=Find(y); p[x]=y; } int num[N]; int G[N][N]; void Traverse(int u) { for(int v=1;v<=50;v++) if(G[u][v]>0) { G[u][v]--,G[v][u]--; Traverse(v); printf("%d %d\n",v,u); //不可以顺序打印 } } void solve() { if(kase>0) puts(""); printf("Case #%d\n",++kase); int pp=-1; for(int i=1;i<=50;i++) { if(num[i]==0) continue; if(num[i]&1) //存在奇度数结点 { puts("some beads may be lost"); return ; } if(pp==-1) { pp=Find(i); continue; } if(pp!=Find(i)) //不联通 { puts("some beads may be lost"); return ; } } Traverse(pp); } void init() { memset(p,-1,sizeof(p)); memset(num,0,sizeof(num)); memset(G,0,sizeof(G)); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); init(); for(int i=0;i<n;i++) { int u,v; scanf("%d%d",&u,&v); num[u]++,num[v]++; G[u][v]++,G[v][u]++; //无向图 Union(u,v); } solve(); } }
转载于:https://www.cnblogs.com/Just–Do–It/p/7448932.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108202.html原文链接：https://javaforall.net
