Watchcow（POJ2230+双向欧拉回路+打印路径）

题目：

题意：给你m条路径，求一条路径使得从1出发最后回到1，并满足每条路径都恰好被沿着正反两个方向经过一次。

思路：由于可以回到起点，并且题目保证有解，所以本题是欧拉回路。输出路径有两种方法，一种是递归实现，一种是用栈处理，不过两种速度差了1s，不知道是不是我递归没处理好~

Watchcow（POJ2230+双向欧拉回路+打印路径）

代码实现如下（第一种为栈输出路径，对应797ms，第二种为递归，对应1782ms):

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<ll, ll> pll;

 typedef pair<ll, int> pli;

 typedef pair<int, ll> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long ull;

 #define lson i<<1

 #define rson i<<1|1

 #define bug printf("*********\n");

 #define FIN freopen("D://code//in.txt", "r", stdin);

 #define debug(x) cout<<"["<<x<<"]" <<endl;

 #define IO ios::sync_with_stdio(false),cin.tie(0);

 const double eps = 1e-;

 const int mod = ;

 const int maxn = 5e4 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const ll INF = 0x3f3f3f3f3f3f3f;

 int n, m, u, v, tot, top, t;

 int head[maxn], stc[maxn*], ans[maxn*], vis[maxn*];

 struct edge {

     int v, next;

 }ed[maxn*];

 void addedge(int u, int v) {

     ed[tot].v = v;

     ed[tot].next = head[u];

     head[u] = tot++;

     ed[tot].v = u;

     ed[tot].next = head[v];

     head[v] = tot++;

 }

 void eulergraph() {

     stc[++top] = ;

     while(top > ) {

         int x = stc[top], i = head[x];

         while(i != - && vis[i]) i = ed[i].next;

         if(i != -) {

             stc[++top] = ed[i].v;

             head[x] = ed[i].next;

             vis[i] = ;

         } else {

             top--;

             ans[++t] = x;

         }

     }

 }

 int main() {

     //FIN;

     scanf("%d%d", &n, &m);

     tot = top = t = ;

     memset(stc, , sizeof(stc));

     memset(ans, , sizeof(ans));

     memset(vis, , sizeof(vis));

     memset(head, -, sizeof(head));

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

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

         addedge(u, v);

     }

     eulergraph();

     for(int i = t; i; i--) printf("%d\n", ans[i]);

 }

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<ll, ll> pll;

 typedef pair<ll, int> pli;

 typedef pair<int, ll> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long ull;

 #define lson i<<1

 #define rson i<<1|1

 #define bug printf("*********\n");

 #define FIN freopen("D://code//in.txt", "r", stdin);

 #define debug(x) cout<<"["<<x<<"]" <<endl;

 #define IO ios::sync_with_stdio(false),cin.tie(0);

 const double eps = 1e-;

 const int mod = ;

 const int maxn = 1e4 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const ll INF = 0x3f3f3f3f3f3f3f;

 int n, m, u, v, tot, top, t;

 int head[maxn], vis[maxn*];

 struct edge {

     int v, next;

 }ed[maxn*];

 void addedge(int u, int v) {

     ed[tot].v = v;

     ed[tot].next = head[u];

     head[u] = tot++;

     ed[tot].v = u;

     ed[tot].next = head[v];

     head[v] = tot++;

 }

 void eulergraph(int x) {

     for(int i = head[x]; ~i; i = ed[i].next) {

         if(!vis[i]) {

             vis[i] = ;

             eulergraph(ed[i].v);

         }

     }

     printf("%d\n", x);

 }

 int main() {

     //FIN;

     scanf("%d%d", &n, &m);

     tot = top = t = ;

     memset(vis, , sizeof(vis));

     memset(head, -, sizeof(head));

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

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

         addedge(u, v);

     }

     eulergraph();

     return ;

 }