poj 2230 Watchcow 欧拉回路

缘起

日常浪费生命 poj 2230 Watchcow

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
有一个人每晚要检查牛场，牛场内有m条路（无向图），他担心会有遗漏，就每条路检查两次，且每次的方向不同，要
求你打印他行走的路径（必须从1开始，而且回到1），打印一条即可。注意,两点之间的边可能不止一条。 输入保证
一定存在。

【输入】
第一行是两个正整数N和M 
2 <= N <= 10,000, 1 <= M <= 50,000
然后是M行，每行2个正整数表示此两点之间有边

【输出】
输出欧拉路径.

【样例输入】
4 5
1 2
1 4
2 3
2 4
3 4

【样例输出】
1
2
3
4
2
1
4
3
2
4
1

【限制】
3s

【是否接受special judge】
是

红果果的欧拉回路啊~ 而且题目都保证存在. 连检查是否存在不需要了~ 直接用fleury 艹它!

因为每条路要走两边——正反各一遍, 所以可以将图视作有向图. 每条边拆成2条弧. 注意，fleury算法是可以跑在有向图上的!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,m,cnt,head[10005],ans[100005],top;
bool v[100005];
struct Arc
{
	int from,to,nxt; // 不需要len,len不重要
	Arc(){}
	Arc(int from, int to, int nxt):from(from), to(to), nxt(nxt){}
}g[100005];

void addArc(int a,int b) // 头插弧 a->b
{
	g[cnt].from = a, g[cnt].to = b, g[cnt].nxt = head[a];
	head[a] = cnt++;
}

void dfs(int i) // fleury
{
	for (int x = head[i]; ~x; x = g[x].nxt)
	{
		if (!v[x])
		{
			v[x] = true;
			dfs(g[x].to);
			ans[top++] = x;
		}
	}
}

int main()
{	
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d%d", &n, &m);
	memset(head, -1, sizeof(head));
	while(m--)
	{
		int a,b;
		scanf("%d%d", &a, &b);
		addArc(a,b);
		addArc(b,a);
	}
	dfs(1);
	for (int i = top-1; ~i; i--)
	{
		printf("%d\n", g[ans[i]].from);
	}
	puts("1");
	return 0;
}

ac情况（水过水过~ 跑了一秒多, fleury真特么慢!）

Status Accepted
Time 1125ms
Memory 2960kB
Length 850
Lang C++
Submitted 2019-09-07 09:59:46
Shared
RemoteRunId 20840281