[UVA 10054] The Necklace

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;
}


[UVA 10054] The Necklace

上一篇:UML——协作图


下一篇:VS2012,更新补丁后的残忍--创建项目未找到与约束匹配的导出