HIHO #1182 : 欧拉路·三（有向图 输出欧拉路径）

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

题目链接

A)建图是巧妙，使用边表示每一个数字，那么就是走完每一个边一次再回到起点，便是求欧拉回路
B)建图是有向图，建图需要注意，同时，输出的时候逆序输出
C)path保存的是完整的路径，输出的时候只需&1即可

#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 = 1<<15+2;
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],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) {cl(vis,false);for(int i=0;i<maxn;i++)G[i].clear();es.clear();top=0;int x = 1<<(n-1);for(int i=0; i<(1<<n-1); i++) {int j=i<<1;int xx = 1<<(n-1);j = j&(xx-1);addEdge(i,j);addEdge(i,j+1);}dfs(0);for(int i=top-1;i>=1;i--){printf("%d",path[i]&1);}printf("\n");}return 0;
}

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

---