uva 10054 The Necklace（欧拉回路）-白红宇

uva 10054 The Necklace（欧拉回路）

阅读量：6404 次

发布时间：2019-06-23

本文共 3059 字，大约阅读时间需要 10 分钟。

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 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 ( $5 \leN \le 1000$ ) 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 $1 \le i \le N 1$ , 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

251 22 33 44 55 652 12 23 43 12 4

Sample Output

Case #1some beads may be lost Case #22 11 33 44 22 2

题目大意：给出一堆珠子，每个珠子有两个颜色，要求判断所给出的珠子是否能连成一个环状的项链。（可以的话要输出）

解题思路：典型的欧拉回路问题，满足1、所有点的入度要等于出度；

2、所有点的联通（这道题目数据没有卡这里）

输出的时候要注意点的自身形成一个环

比如：

1 -> 2

2 -> 3

3 -> 1

2 -> 4

4 -> 2

欧拉回路需要逆序输出。

#include
    
     #include
     
      #define M 52int num[M];int map[M][M];int n;int get_fa(int x){	return num[x] != x?get_fa(num[x]):x;}void print(int k){	for (int i = 0; i < M; i++)		if (map[k][i]){			map[k][i]--;			map[i][k]--;			print(i);			printf("%d %d\n", i , k);		}}int main(){	int t, bo, k = 1;	int f[M];	scanf("%d" ,&t);	while (t--){		// Init.		memset(f, 0, sizeof(f));		memset(map, 0, sizeof(map));		bo = 0;		for (int i = 0; i < M; i++)			num[i] = i;        		// Read.		scanf("%d", &n);		for (int i = 0; i < n; i++){			int a, b;			scanf("%d%d", &a, &b);			f[a]++;			f[b]++;			map[a][b]++;			map[b][a]++;            num[get_fa(a)] = get_fa(b);		}        		// Find.		int god = 0;    	for (int i = 0; i < M; i++)			if (f[i] && get_fa(i) == i)			{				god = i;				break;			}        		// Judge.		for (int i = 0; i < M; i++){			bo += f[i] % 2;			if (f[i] && god != get_fa(i))					bo++;		}        		// Printf.		printf("Case #%d\n", k++);		if (bo > 0)			printf("some beads may be lost\n");		else			print(god);		if (t)			printf("\n");	}	return 0;}

转载地址：http://vsjea.baihongyu.com/

你可能感兴趣的文章