Fleury算法 求欧拉回路

Fleury算法

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 bool e[maxn][maxn];

 int n,m;

 stack<int>stk;

 void dfs(int u){

     stk.push(u);

     for(int i = ; i <= n; i++){

         if(e[u][i]){

             e[u][i] = false;

             e[i][u] = false;

             dfs(i);

             break;

         }

     }

 }

 void Fleury(int x){

     while(!stk.empty()) stk.pop();

     stk.push(x);

     int i;

     while(!stk.empty()){

         int u = stk.top();

         stk.pop();

         for(i = ; i <= n; i++)

             if(e[u][i]) break;

        if(i <= n) dfs(u); else printf("%d ",u);

     }

     puts("");

 }

 int main() {

     int u,v,cnt,degree,st;

     while(~scanf("%d %d",&n,&m)){

         memset(e,false,sizeof(e));

         for(int i = ; i < m; i++){

             scanf("%d %d",&u,&v);

             e[u][v] = e[v][u] = true;

         }

         cnt = ;

         st = ;

         for(int i = ; i <= n; i++){

             for(int j = ,degree = ; j <= n; j++)

                 if(e[i][j]) degree++;

             if(degree&){

                 st = i;

                 cnt++;

             }

         }

         if(cnt ==  || !cnt) Fleury(st);

         else puts("No Euler path");

     }

     return ;

 }