HIHO #1181 : 欧拉路·二（fleury算法输出欧拉路径）

本文主要是介绍HIHO #1181 : 欧拉路·二（fleury算法输出欧拉路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

伪代码

DFS(u):While (u存在未被删除的边e(u,v))删除边e(u,v)DFS(v)EndPathSize ← PathSize + 1Path[ PathSize ] ← u

点之间可能存在多条边，所以存边，然后标记每条边的标号，还是一个常见的存边的表示法

#include<bits/stdc++.h>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define LL long long
#define pb push_back
#define gcd __gcd#define For(i,j,k) for(int i=(j);i<k;i++)
#define lowbit(i) (i&(-i))
#define _(x) printf("%d\n",x)const int maxn = 5e3+100;
const int inf  = 1 << 28;struct Edge{int from,to;
};vector<Edge> es;
vector<int> G[maxn];
void addEdge(int from,int to){es.pb((Edge){from,to});int m = es.size()-1;G[from].pb(m);G[to].pb(m);
}int n,m;
int path[maxn*maxn],top;bool vis[maxn];void dfs(int u) {for(int i=0; i<G[u].size(); i++) {int p = G[u][i];if(vis[p])continue;vis[p]=true;int v = es[G[u][i]].to;dfs(u==v?es[G[u][i]].from:v);}path[++top] = u;
}
int main() {while(cin>>n>>m) {cl(vis,0);top=0;for(int i=0;i<maxn;i++)G[i].clear();es.clear();for(int i=0; i<m; i++) {int x,y;cin>>x>>y;addEdge(x,y);}dfs(1);for(int i=1; i<=top; i++) {printf("%d%c",path[i],i==top?'\n':' ');}}return 0;
}

这篇关于HIHO #1181 : 欧拉路·二（fleury算法输出欧拉路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---