本文从WordPress迁移而来, 查看全部WordPress迁移文章
强连通分量
题意:给一个有向图,对于图中任意两个点u,v,如果从u能到v,或者,v能到u,则这对顶点是可行的,如果图中任意一对顶点都是可行的,可以输出Yes,否则输出No
这个的话,就不是裸的强连通分量了。思考一下,对于一个有向图而言,里面的强连通分量肯定满足题目的条件,因为强连通分量内是u可到v,而且,v可到u,所以我们第一步工作就是强连通分量缩点,变为一个DAG。对于这个DAG里面的任意两个点U,V,如果满足题目的条件,那么点U,V里面包含的原图的点也肯定是满足的
所以问题转化为怎么判断这个DAG是满足题目条件呢?其实判断很简单,就是看这个DAG里面有多少个点的入度为0,多少个点出度为0
如果DAG中,有2个或2个以上的点的入度为0,那么这个DAG就是No,因为这说明有两个点是无法“进去”的,没有点能“进去”U,也没有点能“进去”V,那么这两个点肯定互相不能“进去”,即到达
如果DAG中,有2个或2个以上的点的出度为0,那么这个DAG就是No,因为说明这两个点是无法“出去的”。
反证法,点U和V,它们出度都是0,假设它们满足题目条件,从U能到V,或者从V能到U
- 因为点U出度为0,所以无法“出去”,它肯定无法到达V
- 因为点V出度为0,所以无法“出去”,它肯定无法到达U
- 综上,点U无法到达V,点V无法到达点U,与假设矛盾,所以与题目不成立
那么什么最后一个问题,如果这个DAG,入度为0的点的个数 <= 1 , 出度为0的点的个数 <= 1 , 它就一定Yes吗?
这个就比较容易想了,首先,1个DAG中,不可能所有点都有入度,即入度为0的点个数为0,是不可能发生的。同样的,可能所有点都有出度,即出度为0的点个数为0,是不可能发生的
那剩下的情况就是,1个点入度为0为u,1个点出度为0为v。这个图,呈现一个“橄榄形”。如果从点u走到点v,能经过所有的点,那么就是Yes,否则是No。因为无法经过所有的点的话,说明图中出现了“分叉”,这种“分叉”必定导致两个点互相不可达。而从u到v,经过所有点,其实就是把这个DAG变成了一条链,就是判断这个DAG是否存在一条链贯穿所有点
怎么判断链呢?可以转化为拓扑排序,或者DP最长路
拓扑:拓扑排序可能有多种结果,但是如果是一个最长链,结果则是唯一的,结果要唯一,其实就是从初始化开始,到后面的任何一次删弧入队操作,都是保证了每次都只有一个元素入队,即永远只有一个元素的入度为0,如果中途有一次出现了有两个点入度为0,那么其实代表出现了一种“分叉”
而且拓扑排序可以综合掉前面的情况,不需要特判DAG有几个点入度为0,出度为0,直接拓扑,在拓扑过程就已经判断了
DP:d[i]表示从i点(缩点后的i点)出发能走出的最长路,只要有一个点,d[i] = N , 说明这个点出发能走遍所有点,那么就是一个最长链,输出Yes,否则No
两个代码,前面部分都是相同的,即Tarjan缩点,只有后面不同,一个是int topsort(), 一个是int DP()
不过,这题的数据太弱了,一开始我想错了判断链的地方,写了个很简单的,后来测试错得一塌糊涂,但是POJ还是给了我AC…….
拓扑
1 | //判断整个图是不是强连通分量 |
DP
1 | //判断整个图是不是强连通分量 |