Codeforces 118E Bertown Roads

这是一个图论杂题，似乎涉及图的遍历。

原题地址：http://codeforces.com/problemset/problem/118/E

题目的大意是有 1 个含 n 个地点，m 条路的连通无向图，需要把它的每一条边都变成有向的，然后使得它依然连通。问你之后每一条边的方向是什么。

如果没有方案，输出 0; 如果有方案，输出其中的任何一个。输出方案的方式是每行两个数 a, b, 表示某条路的方向是从 a 到 b. 然后你可以按照任何顺序输出这些路。

样例输入是：

6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5

样例输出是：

1 2
2 3
3 1
4 5
5 6
6 4
4 2
3 5

第二组样例输入是：

6 7
1 2
2 3
1 3
4 5
4 6
5 6
2 4

第二组样例输出是：

0

我一开始的想法比较复杂，但是感觉还是没有啥错的。后来看了一下别人的代码，真是吓一跳，短。

那题的思路就借鉴了 Kosaraju 算法的思想，首先在无向图上遍历一遍，不要遍历重复的点，但是遍历到的边都要记下遍历时的方向，并且记下方向的边也无需再次遍历。然后我们可以得到一个有向图。显然这个有向图可以从起始点遍历到其它任何一个点。

Kosaraju 的思想有一部分是，如果一个有向图，从某个点可以到任意另一个点的话，那么，将这个有向图的所有的边反转，还能够中这个顶点走到任意另一个顶点，那么，原来的有向图是连通的。

然后，如果连通，就可以把所有的有向边输出；如果不连通，就输出 0.