用 tarjan 遍历整个图,如果某个点是割点,当且仅当以下两种情况

  1. 当前点是根节点,且当前节点出发独立的联通分量至少有两个
  2. 当前点不是根节点,且当前节点出发的独立分量能回溯到的最早的点在当前节点之后

转换过来就是下面两个条件

  1. u == root && child >= 2
  2. u != root && low[v] >= dfn[u]

其他与 tarjan 算法无异。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×