首页 > 代码库 > Fleury算法 求欧拉回路

Fleury算法 求欧拉回路

Fleury算法

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 1000;18 bool e[maxn][maxn];19 int n,m;20 stack<int>stk;21 void dfs(int u){22     stk.push(u);23     for(int i = 1; i <= n; i++){24         if(e[u][i]){25             e[u][i] = false;26             e[i][u] = false;27             dfs(i);28             break;29         }30     }31 }32 void Fleury(int x){33     while(!stk.empty()) stk.pop();34     stk.push(x);35     int i;36     while(!stk.empty()){37         int u = stk.top();38         stk.pop();39         for(i = 1; i <= n; i++)40             if(e[u][i]) break;41        if(i <= n) dfs(u); else printf("%d ",u);42     }43     puts("");44 }45 int main() {46     int u,v,cnt,degree,st;47     while(~scanf("%d %d",&n,&m)){48         memset(e,false,sizeof(e));49         for(int i = 0; i < m; i++){50             scanf("%d %d",&u,&v);51             e[u][v] = e[v][u] = true;52         }53         cnt = 0;54         st = 1;55         for(int i = 1; i <= n; i++){56             for(int j = 1,degree = 0; j <= n; j++)57                 if(e[i][j]) degree++;58             if(degree&1){59                 st = i;60                 cnt++;61             }62         }63         if(cnt == 2 || !cnt) Fleury(st);64         else puts("No Euler path");65     }66     return 0;67 }

 

Fleury算法 求欧拉回路