SkyWT

Fighting 2019!

在一幅无向图中,如果删除了一个点,导致图分成了两个或多个联通块(强连通分量),那么这个点就是割点。怎么求这样的点呢?最原始暴力的方法就是每次枚举一个点,删除,跑一遍最短路。今天我们可以用更高级的 Tarjan 算法 \displaystyle \Theta (N) 求解。

Read more...

发布 0 条评论