[题解]UVA10054 The Necklace

链接：http://vjudge.net/problem/viewProblem.action?id=18806

描述：给出一堆珠子，每个珠子有两种颜色，有一端颜色相同的珠子可以串在一起，问是否可以把所有珠子串在一起，并求其中一种方案。

思路：欧拉回路

以颜色作为节点，以珠子作为边建图，无向图。

下面是我的实现：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MaxC 55
int Edge[MaxC][MaxC],Du[MaxC];
int M,Cnt;
bool vis[MaxC][MaxC];
inline void Addedge(int u,int v)
{
    Edge[u][v]++;Edge[v][u]++;
}
void Solve(int u)
{
    int v;
    for(v=1;v<=M;)
    {
        if(Edge[u][v])
        {
           // vis[u][v]=vis[v][u]=1;
            Edge[u][v]--;Edge[v][u]--;
            Solve(v);
            printf("%d %d",v,u);
            if(u!=M)
                printf("\n");
            if(u==M)
            {
                Cnt--;
                if(Cnt)
                    printf("\n");
            }
        }
        else v++;
    }
}
int main()
{
    int T,N;
    int i,j,u,v;
    scanf("%d",&T);
    for(i=1;i<=T;i++)
    {
        if(i>1) printf("\n");
        printf("Case #%d\n",i);
        scanf("%d",&N);
        memset(Du,0,sizeof(Du));
        memset(Edge,0,sizeof(Edge));
        memset(vis,0,sizeof(vis));
        M=0;
        for(j=1;j<=N;j++)
        {
            scanf("%d%d",&u,&v);
            Addedge(u,v);
            Du[u]++;Du[v]++;
            if(M<u) M=u;
            if(M<v) M=v;
        }
        for(j=1;j<=M;j++)
            if(Du[j]%2)
                break;
        if(j<=M)
        {
            printf("some beads may be lost\n");
            continue;
        }
        Cnt=Du[M];
        Solve(M);
    }
    return 0;
}

给一个我写的数据生成器：http://www.cnblogs.com/CQBZOIer-zyy/p/3818078.html