Tarjan 的实际应用 — 题解集合

题解 for Luogu P2661，P2746，P2812，P2194，P2169，P2835，P2002以上题目都可以用 Tarjan 求强连通分量来做。

强连通分量（SCC）与缩点

前面这篇文章着重介绍了 Tarjan 算法找强连通分量的方法。此文章着重介绍缩点。寻找 SCC 的方法依然是 Tarjan 算法。

强连通与强连通分量（SCC）首先需要知道它们的定义……强连通：有向图中两个点可以相互到达，那么它们就是强连通的。强连通分量：有向图中的一组点可以相互到达（就是多个点可以相互到达）缩点：把强连通分...

关于 SPFA，它死了。以前的最短路算法一直都用的 SPFA，说到原因，那就是兼容性和速度都比较好（而且好写），毕竟 Dijkstra 不能处理存在负环的情况。