The Necklace 【UVA - 10054】【欧拉回路详解】

题目链接1

题目链接2

  题目求的是一串珠子，要让它们首尾相互照应才能串起来，并且，最后要连成一个环，使得最后的珠子的尾与第一个珠子的头相互对应。

  那么，这道题就是道求欧拉回路的题了，我们要先判断这是不是能够构成欧拉回路，这是个无向图，再对于需要首尾链接的欧拉回路，我们所有的节点的度都必须是偶数，如果有节点的度不是偶数，说明就会跳不出这个点，就形成不了欧拉图了。

  再者，对于怎么搜的问题，我们已经知道这是个欧拉图了，我们从任意节点开始进入这幅图，那么既然都能构成欧拉回路，所以我们先记录每条边的出现次数，然后每放进去就删除一条，如果没有下一个点的走法，就把这条边的两个端点输出，但是呢，这里需要倒叙输出，就是先进去的放在后面，例如dfs()中的查询是u->v但是我们输出得是v->u，这里当然是有原因的，我们遇到一个多下一个后继点的点，我们都需要返回到这个点，这么解释好像不大好：譬如有点1->2, 1->3, 1->4，说明从1出去有很多节点，我们不能按照顺叙输出，得逆序，不然最后会出现不一样的衔接。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 55;
int N, head[maxN], cnt, edge[maxN][maxN], du[maxN];
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
}path[2005];
void addEddge(int u, int v)
{
    path[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
void dfs(int u)
{
    for(int i=head[u]; i!=-1; i=path[i].nex)
    {
        int v = path[i].to;
        if(edge[u][v])
        {
            edge[u][v]--;
            edge[v][u]--;
            dfs(v);
            printf("%d %d\n", v, u);
        }
    }
}
void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(edge, 0, sizeof(edge));
    memset(du, 0, sizeof(du));
}
int main()
{
    int T;  scanf("%d", &T);
    for(int Cas=1; Cas<=T; Cas++)
    {
        if(Cas>1) printf("\n");
        scanf("%d", &N);
        init();
        int e1, e2;
        for(int i=1; i<=N; i++)
        {
            scanf("%d%d", &e1, &e2);
            addEddge(e1, e2);
            addEddge(e2, e1);
            edge[e1][e2]++;
            edge[e2][e1]++;
            du[e1]++;
            du[e2]++;
        }
        printf("Case #%d\n", Cas);
        bool flag = true;
        for(int i=1; i<=50; i++)
        {
            if(du[i] & 1)
            {
                flag = false;
                printf("some beads may be lost\n");
                break;
            }
        }
        if(flag)
        {
            for(int i=1; i<=50; i++) dfs(i);
        }
    }
    return 0;
}