JustRaincoat Notebook OI/ACM 算法竞赛笔记

双连通分量(DCC)—— Tarjan

双连通分量(DCC)——Tarjan 原理 和 SCC 一样都是在 dfs 生成树上记录 dfn 和 low,在环中编号最小的。 需要做一下概念上的区分: SCC(强连通分量) 是针对有向图的概念。一个SCC内的任意两个节点都可以互相到达(即存在双向路径)。 DCC(双连通分量) 是针对无向图的概念

Administrator Administrator 发布于 2026-06-28

强联通分量(SCC)—— Tarjan

强联通分量(SCC)—— Tarjan 定义 强连通: 在一个有向图 G=(V,E)G = (V, E)

Administrator Administrator 发布于 2026-06-28