My little sister had a beautiful necklace made of colorful beads. Two successive beads in the necklace shared a common color at their meeting point. The figure below shows a segment of the necklace:
But, alas! One day, the necklace was torn and the beads were all scattered over the floor. My sister did her best to recollect all the beads from the floor, but she is not sure whether she was able to collect all of them. Now, she has come to me for help. She wants to know whether it is possible to make a necklace using all the beads she has in the same way her original necklace was made and if so in which order the bids must be put.
Please help me write a program to solve the problem.
Input
The input contains T test cases. The first line of the input contains the integer T.
The first line of each test case contains an integer N ( ) giving the number of beads my sister was able to collect. Each of the next N lines contains two integers describing the colors of a bead. Colors are represented by integers ranging from 1 to 50.
Output
For each test case in the input first output the test case number as shown in the sample output. Then if you apprehend that some beads may be lost just print the sentence ``some beads may be lost" on a line by itself. Otherwise, print N lines with a single bead description on each line. Each bead description consists of two integers giving the colors of its two ends. For , the second integer on line i must be the same as the first integer on line i + 1. Additionally, the second integer on line N must be equal to the first integer on line 1. Since there are many solutions, any one of them is acceptable.
Print a blank line between two successive test cases.
Sample Input
2 5 1 2 2 3 3 4 4 5 5 6 5 2 1 2 2 3 4 3 1 2 4
Sample Output
Case #1 some beads may be lost Case #2 2 1 1 3 3 4 4 2 2 2
#include<cstdio> #include<cstring> using namespace std; #define M 50 int map[M+1][M+1],n; void euler(int u) { for(int v = 1;v <= 50;v++)if(map[u][v]) { map[u][v]--; map[v][u]--; euler(v); printf("%d %d\n",v,u); } } int main() { // freopen("in.txt","r",stdin); int T,step,i,a,b,flag; scanf("%d",&T); for(step = 1;step <= T;step++) { memset(map,0,sizeof(map)); scanf("%d",&n); for(i = 0;i < n;i++) { scanf("%d%d",&a,&b); map[a][b]++;map[b][a]++; map[a][0]++;map[b][0]++; } for(i=1,flag=0;i<=50;i++) if(map[i][0]%2) { flag=1; break; } printf("Case #%d\n",step); if(flag)printf("some beads may be lost\n"); else euler(a); if(step<T)printf("\n"); } return 0; }
相关推荐
这里以构建一个度全部相同的欧拉回路,并输出欧拉回路的路径 1.构建欧拉回路 连通主要是靠树来保证,首先建立一个度为k的完全图,其中会有很多需要主要的地方 (1)首先构造树 =>保证顶点连通 (2)将度的点...
欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
图论- 图的遍历- 欧拉通路与欧拉回路问题.rar
欧拉回路性质与应用探究欧拉回路性质与应用探究欧拉回路性质与应用探究
COMSOL 两相流 欧拉-欧拉 双流体模型
图论——欧拉回路的Fleury算法 根据离散数学教材中思想 实现求欧拉回路。
算法-欧拉回路(HDU-1878)(包含源程序).rar
第八讲-机器人动力学--牛顿-欧拉方程.ppt
欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结,...
关于算法与图论中有向图的欧拉回路的判断,判断一个有向图是否有欧拉回路
2022级图论-欧拉回路和最短路_题解
实现了欧拉回路的程序实现即遍历图输出欧拉回路
算法-数论- 欧拉函数.rar
自己用C写的无向图找欧拉回路的一个例子。主要用于数据结构的学习
对欧拉回路的实验报告,有利于大家更好地理解欧拉回路,对要实验报告的人很适合。本算法使用c语言编写的 如需其他语言请自行更改。
找欧拉回路,本程序实现了对一个欧拉图形找其欧拉回路
实 验 报 告(2019 / 2020 学年 第 一 学期) 课程名称 离散数学 实验名称 图的生成及欧拉回路的确定 实验时间 2021 年 1
Catenyms poj hoj 欧拉回路输出路径
实验_38_如何构建欧拉回路.pdf