hiho一下 第五十周（歐拉路徑）50

///

作者：tt267

聲明：本文遵循以下協定自由轉載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0

檢視本文更新與讨論請點選：http://blog.csdn.net/tt2767/article/details/46493073

///

比賽連結：http://hihocoder.com/contest/hiho50

題目連結：http://hihocoder.com/problemset/problem/1181

（比賽過期後可用）

題目裡的提示解釋的很清楚了，就是僞代碼略坑。。

注意重邊的問題，WA了我好幾次

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<sstream>
#include<string>
#include <iterator>
#include<vector>
#include<map>
#include <stack>
#include<queue>
#include<set>
#include <list>
#include<functional>
#include<numeric>
using namespace std;
typedef  long long int LL;
const int INF = ;
const long double PI = acos() * ;

const int N = ;//不要太大，記憶體可能超限
stack<int>S;
int edge[N][N];
int n,m;
bool flag = true;

void Fleury(int start);
void dfs(int x);

int main()
{
    int u,v;
    memset(edge,,sizeof(edge));
    scanf("%d%d",&n,&m);
    for(int i=; i<m; i++)
    {
        scanf("%d%d",&u,&v);
        edge[u][v]++;
        edge[v][u]++;   //記錄邊的個數，可能有重邊
    }
    int start=;
    for(int i=; i<=n; i++)//判斷歐拉回路的起點
    {
        int degree=;
        for(int j=; j<=n; j++)
        degree+=edge[i][j];
     if(degree&)
        {
            start=i;
            break;  //取第一個就可以了
        }
    }
    Fleury(start);
    return ;
}
void Fleury(int u)
{
    S.push(u);
    while(!S.empty())
    {
        bool bridge = false;
        for(int i=; i<=n; i++)//判斷一下是否有支路，就是判斷下有木有橋
        {
            if(edge[S.top()][i]>)
            {
                bridge=true;
                break;
            }
        }
        if(bridge)
        {
            int v=S.top();S.pop();
            dfs(v); //如果有，就dfs
        }
        else
        {
            if(flag)//使輸出尾部沒有空格
            {
                printf("%d",S.top());
                flag = false;
            }
            else
                printf(" %d",S.top());

            S.pop();
        }
    }
    puts("");
}


void dfs(int u)
{
    S.push(u);
    for(int v=; v<=n; v++)
    {
        if(edge[u][v]>)
        {
            edge[u][v]--;//删除此邊
            edge[v][u]--;
            dfs(v);
            break;
        }
    }
}