大家好,又见面了,我是全栈君。
题目大意:我的妹妹有一串由各种颜色组成的项链。 项链中两个连续珠子的接头处共享同一个颜色。 如上图, 第一个珠子是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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108202.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...