首页 > 代码库 > 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算法 求欧拉回路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。