POJ 2230 Watchcow（欧拉回路：输出点路径）

题目大意：给你n个点m条边，Bessie希望能走过每条边两次，且两次的方向相反，让你输出以点的形式输出路径。

解题思路：其实就是输出有向图的欧拉路，只是让你以点的形式输出。建图的时候，输入a,b直接建立（a,b）和（b,a）正反两条边，然后dfs递归遍历即可。注意输出点的位置：在边遍历完之后输出，原理暂时还没搞懂。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stack>
 5 #define CLR(arr,val)  memset(arr,val,sizeof(arr))
 6 using namespace std;
 7 const int N=1e5+5;
 8 const int M=1e5+5;
 9 const int INF=0x3f3f3f3f;
10 
11 struct node{
12     int to,next;
13 }edge[M];
14 
15 int idx;;
16 int head[N];
17 bool vis[N];
18 
19 void init(){
20     idx=1;
21     CLR(head,0);
22     CLR(vis,false);
23 }
24 
25 void addedge(int u,int v){
26     edge[idx].to=v;
27     edge[idx].next=head[u];
28     head[u]=idx++;
29 }
30 
31 void dfs(int u){
32     for(int &j=head[u];j;j=edge[j].next){
33         node t=edge[j];
34         if(!vis[j]){
35             vis[j]=true;
36             dfs(t.to);
37             //不知道这样为什么错。。。先记着吧 
38             //printf("%d
",t.to);
39         }
40     }
41     printf("%d
",u);
42 }
43 
44 int main(){
45     init();
46     int n,m;
47     scanf("%d%d",&n,&m);
48     for(int i=1;i<=m;i++){
49         int a,b;
50         scanf("%d%d",&a,&b);
51         addedge(a,b);
52         addedge(b,a);
53     }
54     dfs(1);
55     return 0;
56 }