uva 10054 The Necklace 欧拉回路

缘起

日常浪费生命 uva 10054 The Necklace

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
一条项链，珠子的颜色各异, 相邻的2个珠子的一端颜色相同. 例如下图
可惜有一天，项链断了. 珠子散落一地, 只收集了部分珠子. 问你能不能按照此规则串成一串.
如果可以的话, 输出一种顺序。

【输入】
多样例. 第一行是样例数. 每个样例以一个N开头（5 ≤ N ≤ 1000）表示珠子的个数. 然后N行，两个[1,50]
内的整数表示颜色. 

【输出】
对于每个样例. 如果不行的话，输出"some beads may be lost", 如果行的话，输出任何一种即可
两个样例之间有空行

【输入样例】
2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4

【输出样例】
Case #1
some beads may be lost

Case #2
2 1
1 3
3 4
4 2
2 2

【限制】
1s

【是否接受special judge】
是

不超过50个顶点的无向图. 求欧拉路径. 首先使用并查集判断无向图是否连通. 然后跑fleury

代码要是不清楚的话，参见【1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//#include "stdafx.h"
#include <stdio.h>
#include <vector>
using namespace std;
#include <string.h>
//#define LOCAL
typedef pair<int,int> P;
typedef vector<P>::iterator vit;

int n,f[55],deg[55],start,ans[1005], top;
vector<P> g[55];
bool v[1005],used[55];

struct Bead
{
	int a,b;
}bb[1005];

int getf(int i)
{
	return f[i]<0?i:f[i] = getf(f[i]);
}

void merge(int i, int j)
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj)
	{
		return;
	}
	if (f[fi]<f[fj])
	{
		f[fi]+=f[fj];
		f[fj] = fi;
	}
	else
	{
		f[fj]+=f[fi];
		f[fi] = fj;
	}
}

bool ok()
{
	for (int i = 1; i<=50; i++)
	{
		if (deg[i]&1)
		{
			return false;
		}
		if (used[i])
		{
			start = i;
		}
	}
	return true;
}

void dfs(int i)
{
	for (vit x = g[i].begin(); x!=g[i].end(); x++)
	{
		if (!v[x->second])
		{
			v[x->second] = true;
			dfs(x->first);
			ans[top++] = x->second;
		}
	}
}

int main()
{	
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	for (int i = 1; i<=kase; i++)
	{
		memset(f, -1, sizeof(f));
		memset(v, 0, sizeof(v));
		memset(deg, 0, sizeof(deg));
		memset(used, 0, sizeof(used));
		top = 0;
		for (int i = 1; i<=50; i++)
		{
			g[i].clear();
		}
		if (i>1)
		{
			puts("");
		}
		printf("Case #%d\n", i);
		scanf("%d",&n);
		for (int i = 1; i<=n;i++)
		{
			scanf("%d%d", &bb[i].a, &bb[i].b);
			g[bb[i].a].push_back(P(bb[i].b, i));
			g[bb[i].b].push_back(P(bb[i].a, i));
			deg[bb[i].a]++, deg[bb[i].b]++;
			used[bb[i].a] = used[bb[i].b] = true;
			merge(bb[i].a, bb[i].b);
		}
		if (!ok())
		{
			puts("some beads may be lost");
			continue;
		}
		dfs(start); // 因为要保证存在的是欧拉回路而不仅仅是欧拉路径,所以这里从任何一个顶点开始都是可以的
		for (int i = top-1; ~i; i--)
		{
			printf("%d %d\n", start, bb[ans[i]].a+bb[ans[i]].b-start);
			start = bb[ans[i]].a+bb[ans[i]].b-start;
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 190ms
Length 1800
Lang C++11 5.3.0
Submitted 2019-09-07 11:01:12
Shared
RemoteRunId 23877472

参考

【1】https://yfsyfs.github.io/2019/09/06/hihocoder-1181-%E6%AC%A7%E6%8B%89%E8%B7%AF%C2%B7%E4%BA%8C-Fleury%E7%AE%97%E6%B3%95/