ACM – Uva10054 – 欧拉回路

点击量:33

问能不能拼接一条项链,条件是首尾相同构成环。

这个题的坑在:
1. 虽然保证连通,但是不一定每个颜色都有,所以单纯的暴力euler(1)是很愚蠢的。
2. 题目本身是要求顺序输出的,也就是dfs不能回溯,如果回溯,为了保证准确性,需要交换uv的位置来保证。
3. 通过统计出度入度判断是否满足欧拉回路。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
int n;
const int maxn = 1000+10;
int g[60][60];
void euler(int u)
{
    for(int v = 1; v <= 50; v++) if(g[u][v])
    {
        g[u][v]--, g[v][u]--;
        euler(v);
        printf("%d %d\n", v, u);
    }
}
int degree[60];
bool check()
{
    for(int i = 1; i<= 50; i++)
        if(degree[i] % 2) return false;
    return true;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int t;
    cin >> t;
    for(int kase = 1; kase <= t; kase++)
    {
        scanf("%d", &n);
        memset(g, 0, sizeof(g));
        memset(degree, 0, sizeof(degree));
        int f, e;
        for(int i = 0; i < n;i++)
        {
            scanf("%d%d", &f, &e);
            g[f][e] ++;
            g[e][f] ++;
            degree[f]++, degree[e]++;
        }
        printf("Case #%d\n", kase);
        if(check()) for(int i = 1; i<=50; i++) euler(i);
        else puts("some beads may be lost");
        if(kase != t) CR;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注