天天看點

UVA - 10054 The Necklace 歐拉回路

題目大意

給出兩個數字是一條邊,然後找出任意一個歐拉回路。

無向圖歐拉回路的條件:

1. 要聯通

2. 每個節點度必須是偶數

這個簡單題目卡了我一下午,結果就是少輸出了空行;

AC代碼

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MX = +;
int m[MX][MX],IN[MX];
void init()
{
    memset(IN,,sizeof IN);
    memset(m,,sizeof m);
}
void dfs(int st)
{
    for(int i=;i<=;i++) {
        if(m[st][i]<=) continue;
        m[st][i]--;m[i][st]--;
        dfs(i);
        printf("%d %d\n",i,st);
    }
}
void solve(int st,int n)
{
    for(int i=;i<=n;i++) {
        if(IN[i]%==) continue;
        puts("some beads may be lost");
        return ;
    }
    for(int i=;i<=;i++)dfs(i);
}
int main()
{
    int _;//freopen("in.txt","r",stdin);
    scanf("%d",&_);
    for(int cas=;cas<=_;cas++) {
        int n,u,v,st;init();
        scanf("%d",&n);
        for(int i=;i<=n;i++) {
            scanf("%d%d",&u,&v);
            IN[u]++;IN[v]++;st = u;
            m[v][u]++;m[u][v]++;
        }
        printf("Case #%d\n",cas);
        solve(st,n);
        puts("");
    }
    return ;
}