笔记：有向图连通性问题

1.概念

• 强联通：对于u、v而言，u、v是互相可达的
• 强连通图：图G中任意两点均为强联通，即所有点对之间均强联通
• 强联通分量（Strongly Connected Component, SCC）：对于不是强联通图的有向图G，可以划分为多个子图，每个子图内部强联通，且不与图外任意点强连接（因此这些子图已经扩展到了最大）

2.SCC特征

为了解决G中有多少SCC的问题，需要对SCC特征进行研究

• 出度、入度：点必须出度、入度均>0，这样才能够满足强联通
• 把SCC从G中删除，不影响其他SCC、点的强连通性，一个子图内部强联通，外部单向通路（因为没有强连接关系），不形成环路，也就是说一个强联通子图和一个点没有什么本质区别，在不改变的情况下可以抽象为一个点

3.求SCC

1种暴力算法，3种高效算法，复杂度$O(V+E)$

3.1 BFS/DFS

暴力算法，直接对每个点求连通性并且进行比较
时间复杂度%O(V^2 + E)%
算法流程：

1. 先对于每个点进行搜索，求其可达点
2. 求交集，形成一个强联通分量
3. 将第2步求得的联通分量从图中剔除，继续执行1，直到图中不剩余任何点

3.2 Kosaraju算法

关键概念：

• 反图：把图G中所有边反向，建立反图rG。
• 反图性质：rG中SCC和G中SCC数量相同

主要思路：对原图G和反图rG各做一次DFS，以确定SCC数量

1. 使在G上用DFS做拓扑排序，以确定顺序，确定优先级最高的点（剩下的点优先级没确定，只确定最高）
2. 从优先级最高的点开始，在rG上做DFS，目的是求出被隔离的"岛"，因为如果其不能与其他地方（反向）联通，F（或者所在的子图）就不是一个强连通块
3. 删除那个点，继续从最高的点开始搜

算法步骤：

1. 在G上做DFS，把读个我最底层的点标记为最小，回退过程中逐级递增。
2. 反图rG再做一次DFS，标记最大的点到最小的点

Tarjan算法

定理：一个SCC，从其中任何一个点出发，都至少有一条路径能绕回到自己