Tarjan算法求强连通分量/缩点的算法思想

1.对于强连通分量的朴素的理解是:

有向图中互相可达的 不被包含在其他相互可达的子图 的子图 即最大子图。

Tarjan算法的思路是这样的:

我们对有向图进行dfs 如果发现某个结点可以dfs到其祖先结点(dfs树上的祖先结点) 那么说明 从这个结点到这个祖先节点这部分子图 是一个强连通分量。

在实际使用的过程中可根据需要来进行计数或者是给点按强连通分量染色等操作。

缩点是怎么回事呢?

对于在有向图中满足传递性的一些结点的性质(由题目决定的) 则可以将这种问题中的强连通分量视为一个超级结点(其点权计算方式由题目规定和要求而定)

原文地址:https://www.cnblogs.com/leafsblogowo/p/13974341.html