POJ 2762 Going from u to v or from v to u? 

链接：http://poj.org/problem?id=2762

题意：为了让他们的儿子变得更勇敢些，Jiajia 和Wind 将他们带到一个大洞穴中。洞穴中有n 个房间，有一些单向的通道连接某些房间。每次，Wind 选择两个房间x 和y，要求他们的一个儿子从一个房间走到另一个房间，这个儿子可以从x 走到y，也可以从y 走到x。Wind 保证她布置的任务是可以完成的，但她确实不知道如何判断一个任务是否可以完成。为了使Wind 下达任务更容易些，Jiajia 决定找这样的一个洞穴，每对房间（设为x 和y）都是相通（可以从x 走到y，或者可以从y 走到x）的。给定一个洞穴，你能告诉Jiajia，Wind 是否可以任意选择两个房间而不用担心这两个房间可能不相通吗？

思路：这道题的本质是求有向图的单连通性。

单连通性：对于有向图中的任意两点u，v。一定存在从u到v的路径或是从v到u的路径。

1. 先对图求一次强连通分量，然后将每个强连通分量内的点缩成一个点。缩点之后便是一个DAG（有向无环图）。

2. 在DAG中，如果这个树有分叉，对于分叉的两点一定是不能互相到达的。所以该图一定要是一个单链才行。

3. 用拓扑排序来判断是否为单链，每次将入度为0的点加入队列，如果同时两个以上的点入度为0，那么这两个点一定是不能互相到达的，即为非单连通。

代码：

/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include

POJ 2762 Going from u to v or from v to u? （有向图求单连通性）