强连通分量

关注缩点后的 DAG。

如何加最少的有向边，使得 DAG 变得强连通？

设源点（入度为 0 的点）数量为

S

，汇点（出度为 0 的点）数量为

T

，答案：

\max(S, T)

。但注意特判：如果原图只有一个点，那么答案为 0！

证明：

加边数不会小于 max(S, T)

如果小于，就会导致有的源点或者汇点走不到其他点。

存在一种构造方案，使得加边数等于 max(S, T)

从汇点连到源点。不妨设

S \le T

。因为如果

S > T

，那么可以把边取反，转化成

S \le T

，最后把添加的边也取反，就可以得到方案。

设源点集合为

P

，汇点集合为

Q

。

不断进行下面操作，直到不能再进行：

在 $P$ ， $Q$ 中各选一个点 $u$ ， $v$ ，满足 $u$ 的入度为 0，且 $u$ 不能到达 $v$ 。连一条 $v$ 到 $u$ 的边。

由于

u

原本不能到达

v

，连边后保持无环性质不变。

假设这个操作进行了

K

次，则

K \le S - 1

。这是因为每次操作会使

P

中入度为 0 的点的数量减少 1，并且保持 DAG。当 DAG 中入度为 0 的点只有一个时，这个点可以到达所有点。此时就选不出

u

来了。之所以是小于等于

S - 1

而不是等于，是因为原本可能就有一些源点可以到达所有点。

进行

K

次操作后，源点有

S - K

个，汇点有

T - K

个。此时，任意的源点都能到达任何一个点。对于所有汇点，把它和任意的源点相连。需要进行

T - K

次操作。此时，图中所有点都能走到一个汇点，然后走到一个源点，从而走到所有点。因而，图是强连通的。

至此，我们用

T

次操作使得原 DAG 变得强连通。

Ralph and Mushrooms

边权的维护：缩点时再处理，不要在 Tarjan 时处理。
DAG 中从某个起点出发，问路径点权最大值：用拓扑排序，不要用 dfs，因为可能有前向边，导致到同一个点有好几条路径，由于乘法原理，搜索次数会指数增加。拓扑排序时维护数组 reachable[] 表示这个点能否从起点到达。

割点

无向图，没有横叉边，只有树边和返祖边（对于父节点来说它是前向边，对于子节点来说它是返祖边）。判断标准是，到未遍历的点就是树边，否则就是返祖或前向。

判断一个点是不是割点的条件：存在至少一个儿子 v，使得 low[v] >= dfn[u]，即不能回到祖先，那么就是割点；对于遍历的起始节点要特判，如果有至少两个儿子才是割点，否则不是。一个连通分量会一次性搜完。

根据 low 的定义“至多经过一条返祖边”，如果 v 未遍历就是 low[u] = min(low[u], low[v]);，否则 low[u] = min(low[u], dfn[v]);。什么？你担心 v 遍历过，但是是前向边，然后 v 返祖统计不到？没关系，low[v] 会沿着树边传上来。

割边

判断标准：存在至少一个儿子 v，使得 low[v] > dfn[u]。也就是 low[v] == dfn[v]。不用对遍历起始节点进行特判。

对于有重边的情况，对无向边加一个编号，只有编号一样才不能走回头路。

边双连通分量

判断一个边双的根节点：low[u] == dfn[u]。

点双连通分量

割点同属于多个点双。

两个点双最多有一个公共点（割点）。否则这两个就会被合并为一个点双。

算法：要注意的点有点多。

CPP

if (low[v] >= dfn[u]) {
  cnt2++;
  while (true) {
    int t = stk.top(); stk.pop();
    comp[cnt2].push_back(t);
    if (t == v) break;
  }
  comp[cnt2].push_back(u);
}

注意：

判断标准：low[v] >= dfn[u]
出栈一直到 v 而不是到 u
最后要把 u 入栈
要特判独立点（fa == 0 and cnt_son == 0）
不用特判根节点且子节点数为 1 的情况，这种情况下根节点是会被算进一个点双里面的

矿场搭建

如果不把割点计入点双，那么会把一个图切分成割点和很多个连通块。
看这篇题解。找叶子连通块。
本题非常恶心，要分讨一些情况。

Redundant Paths G

边双缩点，答案是叶子数除以 2 上取整。
点双意味着从任意一个点到另外一个点，没有哪个点是必经的，也就是说从任意一个点到另外一个点有至少两条【中间点完全不同】的路径。
边双意味着从任意一个点到另外一个点，没有哪条边是必经的，也就是说从任意一个点到另外一个点有至少两条【经过的边完全不同】的路径。

嗅探器

以其中一个信息中心为根跑 Tarjan，找割点，如果存在一个割点 u，另一个信息中心位于去掉这个割点产生的新连通块（v 的子树）内，那么 u 点就是一个答案。判断的方式是 dfn[另一个信息中心] >= dfn[v]。

专题：连通分量

文章操作