定义:
在有向图中,如果一些顶点中任意两个顶点都能互相到达(间接或直接),那么这些顶点就构成了一个强连通分量,如果一个顶点没有出度,即它不能到达其他任何顶点,那么该顶点自己就是一个强连通分量。
做题的总结吧算是:
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求强连通分量。