UVA – 10054
The Necklace
Time Limit:3000MSMemory Limit:Unknown64bit IO Format:%lld & %llu
Submit
Description
Problem D: The Necklace
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 containsTtest cases. The first line of the input contains the integerT.
The first line of each test case contains an integerN(
) giving the number of beads my sister was able to collect. Each of the nextNlines 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, printNlines 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 lineimust be the same as the first integer on linei+ 1. Additionally, the second integer on lineNmust 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 Input251 22 33 44 55 652 12 23 43 12 4Sample OutputCase #1some beads may be lost Case #22 11 33 44 22 2
Miguel Revilla2000-12-28
Source
Root :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: Graph :: Special Graphs (Others) ::Eulerian GraphRoot :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: Graph :: Special Graphs (Others) ::Eulerian GraphRoot :: AOAPC I: Beginning Algorithm Contests — Training Guide (Rujia Liu) :: Chapter 5. Graph Theory :: Fundamentals ::ExamplesRoot :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume 2. Data Structures ::GraphsRoot :: Prominent Problemsetters ::Rezaul Alam ChowdhuryRoot :: Programming Challenges (Skiena & Revilla) ::Chapter 10
判断欧拉回路的技巧为：所有点的度皆为偶数
这里注意欧拉回路的打印技巧（这里是无向图需要反向打印，，而如果是有向图则需用到栈，，，要压入栈中）
AC代码：
#include <cstdio> #include <cstring>#include <algorithm>using namespace std;int map[55][55];int num[55];int n, cas = 1;void dfs(int x){for(int i = 1; i <= 50; i++)if(map[x][i]){map[x][i]–; map[i][x]–;dfs(i);printf("%d %d\n", i, x);}}int main(){int T;scanf("%d", &T);while(T–){scanf("%d", &n);memset(map, 0, sizeof(map));memset(num, 0, sizeof(num));for(int i = 0; i < n; i++){int a, b;scanf("%d %d", &a, &b);map[a][b]++; map[b][a]++;num[a]++; num[b]++;}int flag = 1, max = 0, maxi = 0;for(int i=1; i<=50; i++){if(num[i] % 2 == 1){ flag = 0; break; }else if(num[i] > max){max = num[i];maxi = i;}}printf("Case #%d\n", cas++);if(flag) dfs(maxi);else printf("some beads may be lost\n");if(T>0) printf("\n");}return 0;}
正如我总是意犹未尽的想起你。
