强联通分量

强联通分量指的是一个有向图中的一部分节点，而任意两个其中的节点互相的路径是相通的，既能从一个节点到另一个节点，也可以从另一个节点到这个节点。

一个图必然能够被分为几个强联通分量的组合，而若是将这几个强联通分量的节点聚合为一个节点，就会得到一个有向无环图，称为分量图。

求出强联通分量的方法如下：

首先对图进行深搜，对于每一个节点记录到达顺序和离开顺序，离开顺序和到达顺序共用一个顺序。

根据这个离开顺序，倒序进行一次深搜，不过深搜的是原图的转置(所有的边的方向都变成原来的反向)。在这种情况下，所能搜索到的必然是一个强联通分量里的所有节点，将这一部分剥离出来后，继续选择剩下的中离开顺序最后的，进行相同的操作。

原理：

首先强联通分量之间的边上的那个节点(假设深搜树走了这条边，否则就选择离开顺序最后的那个节点），设其离开顺序为f1，其所连接的强联通分量也一样，设其离开顺序为f2。

则f1>f2。

如果路径是从f1→f2的。

并且首先搜索了f1，那么肯定会由于这条连接边先去搜索f2的强联通分量的所有节点，后返回该强联通分量的节点并进行离开，所以离开顺序后于f2。

如果首先搜索了f2，那么f2就必然没有一条边能够来到f1强联通分量，否则这两个就是同一个强联通分量了。因此会先把f2搜索完成并离开完成才会去搜索f1，再离开，因此f1>f2。

由于上述原因，当我们选择离开顺序最后的强联通分量，那么这个强联通分量的所有的与其他强联通分量的边都是由该强联通分量指向其他强联通分量的，因此在图的转置中，其将没有任何一条能够前往其他强联通分量的边，因此可以直接分离，并重复操作。