有向图强连通分量SCC(全网最好理解)

2020-10-28 11:25:48 浏览数 (1)

定义:

在有向图中,如果一些顶点中任意两个顶点都能互相到达(间接或直接),那么这些顶点就构成了一个强连通分量,如果一个顶点没有出度,即它不能到达其他任何顶点,那么该顶点自己就是一个强连通分量。

做题的总结吧算是:

1.给定一个有向图,求有多少个顶点是由任何顶点出发都可达的:

    图中只有一个出度为0的点,那么它一定可以由任意点出发可达。SCC缩点后,DFS。

2.至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点。

任何入度不为0的点,一定可以由某个入度为0的点出发可达。

3.有向无环图中,最少添加几条边变成强连通图?

假设有m个入度为0的点,有n个出度为0的点,则至少添加max(m,n)个。

强连通图中不存在入度为0或出度为0的点,所以添加m n条边去掉这些点是一定可行的。

更少的方法,是将两个点连起来,则可以连接出min(m,n)条边,则添加的边数为m n-min(m,n),即为max(m,n).

下期我们会讲Tarjan求强连通分量。

0 人点赞