H

参考：

1，Watchcow（poj 2230）

2，POJ2230 Watchcow【欧拉回路】

例题：

H - Watchcow

题意：给个无向图，求一条回路，经过每条边两次，每次不同向，求无向图每条边恰好经过两次，在回到原点，输出经过的顶点。

　　　　容易转化为有向图欧拉回路每条边经过一次

递归写法（此为求解回路的算法，判断回路是否存在请戳.........挖个坑）

void dfs(int x)
{
	for(int i=0;i<G[x].size();i++)
	{
		if(!G[x][i].flag)
		{
			//	printf("%d
",G[x][i].v);
			G[x][i].flag=1;
			dfs(G[x][i].v);
			//S.push(G[x][i].v);
		}
	}
	ans[++ans1]=x;
	//第一个执行++ans1的一定是递归的终点，
	//也就是欧拉回路的终点（欧拉回路顺序不要紧） 
}

完整代码：

 1 /***********************************************/
 2     int n,m;
 3 stack<int>S;
 4 int ans[2*maxn];
 5 int ans1=0;
 6 struct node{
 7     int v;
 8     int flag;//路径是否被访问 
 9     node(int _v,int _flag):v(_v),flag(_flag){    }
10 };
11 vector<node>G[maxn];
12 void dfs(int x)
13 {
14     for(int i=0;i<G[x].size();i++)
15     {
16         if(!G[x][i].flag)
17         {
18             //    printf("%d
",G[x][i].v);
19             G[x][i].flag=1;
20             dfs(G[x][i].v);
21             //S.push(G[x][i].v);
22         }
23     }
24     ans[++ans1]=x;
25 }
26 
27 int main()
28 {
29 
30     sc2(n,m);
31     for(int i=1;i<=m;i++)
32     {
33         int a,b;
34         sc2(a,b);
35         G[a].push_back(node(b,0));
36         G[b].push_back(node(a,0));
37     }
38     dfs(1);
39     for(int i=1;i<=2*m+1;i++) printf("%d
",ans[i]);
40     return 0;
41 }

View Code