P-欧拉路 uva10054

题目大意：

有一串项链由若干个珠子构成，每两个珠子项链的一端颜色的相同的。

现在给出这些珠子两端的颜色，问用尽所有的珠子能否构成一串项链。

题目思路：

珠子的两端视作点，珠子本身视作边，那么就是从一个点出发遍历完所有的边并且回到起点，因为项链是一个环，所以最后拼接在一起，拼接处的颜色要相同。

那么这就是一个欧拉回路。

需要注意2个地方：

1.判断是否连通，这题的点的序号不一定是连续的；

2.欧拉回路输出路径，需要用到栈来存边，具体见紫书P169。

代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
typedef pair<int,int> pii;
stack<pii> s;
struct edge
{
    int to;
    int id;
    edge(int a,int b)
    {
        to = a;
        id = b;
    }
};
int dg[55];
vector<edge> G[55];
bool vis[1005];
void dfs(int u)
{
    vis[u] = 1;
    for (auto x : G[u])
    {
        if (!vis[x.to])
        {
            dfs(x.to);
        }
    }
}
void euler(int u)
{
    for (auto x : G[u])
    {
        int id = x.id;
        int to = x.to;
        if (!vis[id])
        {
            vis[id] = 1;
            euler(to);
            s.push(pii(u,to));
        }
    }
}
int main()
{
    int T;
    int cas = 0;
    scanf("%d",&T);
    while (T--)
    {
        memset(dg,0,sizeof(dg));
        memset(vis,0,sizeof(vis));
        for (int i = 1;i <= 50;i++) G[i].clear();
        if (cas) puts("");
        printf("Case #%d\n",++cas);
        int n;
        scanf("%d",&n);
        int cnt = 0;
        for (int i = 0;i < n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (!vis[x])
            {
                vis[x] = 1;
                cnt++;
            }
            if (!vis[y])
            {
                vis[y] = 1;
                cnt++;
            }
            dg[x]++;
            dg[y]++;
            G[x].push_back(edge(y,i));
            G[y].push_back(edge(x,i));
        }
        for (int i = 1;i <= 50;i++)
        {
            if (vis[i])
            {
                memset(vis,0,sizeof(vis));
                dfs(i);
                break;
            }
        }
        bool f = 0;
        int num = 0;
        for (int i = 1;i <= 50;i++)
        {
            if (vis[i]) num++;
        }
        if (num != cnt) f = 1;
        for (int i = 1;i <= 50;i++)
        {
            if (dg[i] % 2) f = 1;
        }
        if (f) 
        {
            puts("some beads may be lost");
            continue;
        }
        memset(vis,0,sizeof(vis));
        for (int i = 1;i <= 50;i++)
        {
            if (dg[i])
            {
                euler(i);
                break;
            }
        }
        while (!s.empty())
        {
            auto x = s.top();
            s.pop();
            printf("%d %d\n",x.first,x.second);
        }
    }
    return 0;
}
/*
2
5 
1 2 
2 3 
3 4 
4 5 
5 6
5 
2 1 
2 2 
3 4 
3 1 
2 4
*/