[POJ 2762] 弱连通分量

题意:

给定N个点,E条边的有向图,问图中是否任意两个点u,v都有

(u能到达v)or(v能到达u)

分析:

首先环内的肯定是满足的,所以先缩点。

然后剩下一棵树。

那么从根节点(即缩点后没有入度的点)出发,假设一路走下去是一条链的话(即树没有分叉),而且所有的点都能走到,那么就满足性质。

证明:

1、如果有分叉的话,分叉两边的点不能到达对方。

2、入度为0的点不可能没有,因为已经缩点,不存在环了。

3、入度为0的如果>1,那么两个入度为0的点不能到达对方。

所以,结论就是,只有所有收缩后的点成一长链,才能满足性质。

插曲:

Tarjan居然写错了= =,真想抽自己一下

code:

#include

留下评论

您的电子邮箱地址不会被公开。