题意:
给定N个点,E条边的有向图,问图中是否任意两个点u,v都有
(u能到达v)or(v能到达u)
分析:
首先环内的肯定是满足的,所以先缩点。
然后剩下一棵树。
那么从根节点(即缩点后没有入度的点)出发,假设一路走下去是一条链的话(即树没有分叉),而且所有的点都能走到,那么就满足性质。
证明:
1、如果有分叉的话,分叉两边的点不能到达对方。
2、入度为0的点不可能没有,因为已经缩点,不存在环了。
3、入度为0的如果>1,那么两个入度为0的点不能到达对方。
所以,结论就是,只有所有收缩后的点成一长链,才能满足性质。
插曲:
Tarjan居然写错了= =,真想抽自己一下
code:
#include