The Necklace
题目链接：http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=18472
题目大意：
有一些珍珠（最多1000个），珍珠的两头有颜色（颜色最多50种，编号为1到50），现在问你能否将珍珠按照一定的规律串成一串项链？如果可以，则输出应该如何安排珍珠的先后顺序，否则输出不行。
规律是：前一个珍珠的尾色必须和后一个珍珠的前色相同，而且最后一个珍珠的尾色必须和第一个珍珠的前色相同。
解题思路：
这是一道关于欧拉回路的题目。
首先颜色表示无向图的顶点，而一颗珍珠代表了一条边，（由于珍珠前色和尾色可以互掉，故为无向图）。问该图是否为欧拉回路。
欧拉回路：
欧拉回路的特点是所有顶点的度数均为偶数。 用递归的方式打印欧拉回路。
并查集判连通性：
同时需要用并查集判断连通性。
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int g[55][55], n;
int f[55];
struct node
{
int u, v;
};
stack<node> s;
int find(int x)
{
if (f[x] != x) f[x] = find(f[x]);
return f[x];
}
void euler(int u)
{
for (int v = 1; v <= 50; v++) if (g[u][v])
{
g[u][v]--, g[v][u]--;
euler(v);
node tmp;
tmp.u = u, tmp.v = v;
s.push(tmp);
}
}
int main ()
{
int t, i, j, cas = 1;
cin>>t;
while(t--)
{
cin>>n;
mem(g, 0);
int u, v;
for (i = 1; i <= 50; i++) f[i] = i;
int has[55] = {0}, du[55] = {0}, k;
for (i = 0; i < n; i++)
{
scanf("%d%d", &u, &v);
g[u][v] ++;
g[v][u] ++;
has[u]++, has[v]++;
du[u]++, du[v]++;
f[find(u)] = find(v);
k = u;
}
int sum = 0;
for (i = 1; i <= 50; i++) if (has[i] && f[i] == i) sum++;
if (cas != 1) puts("");
printf("Case #%d\n", cas++);
bool flag = true;
for (i = 1; i <= 50; i++) if (du[i] % 2 == 1)
flag = false;
if (sum != 1 || !flag) puts("some beads may be lost");
else
{
euler(k);
while(!s.empty())
{
node tmp = s.top();
s.pop();
printf("%d %d\n", tmp.u, tmp.v);
}
}
}
return 0;
}