Tarjan算法用途总结

作者：

zhengyh , 2020-06-20 10:41:08 , 所有人可见 , 阅读 837

5

5

所有tarjan算法的时间复杂度都是 $O(n)$

将有向图变成scc最少需要加 $max(缩点后入度为0的点的个数, 缩点后出度为0的点的个数)$
将无向图变成e-dcc最少需要加 $(度数为1的节点个数 + 1) / 2$