图论:Tarjan

前置概念

时间戳:搜索时第几个搜索到这个点。如搜索顺序是1->2->3->6,则6的时间戳为4

对于无向图

连通分量:对于图G来的一个子图中,任意两个点都可以彼此到达,这个子图就被称为图G的连通分量(一个点就是最小的连通分量)

最大连通分量:对于图G的一个子图,这个子图为图G的连通分量,且是图G所有连通分量中包含节点数最多的那个,即为G的最大联通分量

阅读更多