ACM – Uva10054 – 欧拉回路

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

这个题的坑在：

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

#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, , sizeof(g));
        memset(degree, , sizeof(degree));
        int f, e;
        for(int i = ; 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 ;
}