Loading... ### 有向图 1. SCC 强连通分量 - 记录方式：用栈记录 - 处理位置：dfs 尾部 - 处理条件：`low[u]==dfn[u]` 这是一个 SCC。 - 处理方式：把栈到 $u$ 的部分全部取出来变成一个 SCC。 - 多次贡献：否 - 处理逻辑：$u$ 这个点及其 dfs 子树节点若都不能去到更早的地方，那么这个子树最多连通到 $u$，子树内这且不属于是其他 SCC 的点成为 $u$ 这个 SCC，那么用栈记录剩下的点。并且栈中点一定能构成 SCC 若不行则会在其他点统计到。 ### 无向图 1. VDCC 点双连通分量 - 记录方式：用栈记录 - 处理位置：遍历出边的时候 - 处理条件：`low[v]>=dfn[u]` 这是一个 VDCC。若 $u$ 不是无向图根节点，那么出现一次 `low[v]>=dfn[u]` $u$ 就是一个割点；否则要出现两次 $u$ 才能是一个割点。 - 处理方式：把栈到 $v$ 的部分全部取出来加上 $u$ 变成一个 SCC。 - 多次贡献：是 - 处理逻辑：若这个 $v$ 点最多返回到 $u$，那么去掉 $u$ 这一坨就会散开，变得不连通，并且一定会散开，因为不散开肯定其他地方有链接，但是无向图 dfs 不允许这样的事情发生，除非这个时候是 dfs 树根节点，因为去掉根节点下面不会不连通，只有有两次时才会散开。 2. EDCC 边双连通分量 - 记录方式：标记割边 - 处理位置：遍历出边的时候 - 处理条件：`low[v]>dfn[u]` 这是一个 EDCC。 - 处理方式：tarjan 结束后 dfs 遍历图，每次遍历不经过标记的割边，每次遍历到的点形成一个 EDCC。 - 多次贡献：否 - 处理逻辑：若这个 $v$ 点返回不到 $u$，那么去掉 $u\rightarrow v$ 这条边，$v$ 这一坨与 $u$ 就不连通了。 最后修改：2023 年 11 月 10 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏