专题：连通分量

· · 个人记录

强连通分量

关注缩点后的 DAG。

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

设源点（入度为 0 的点）数量为 S，汇点（出度为 0 的点）数量为 T，答案：\max(S, T)。但注意特判：如果原图只有一个点，那么答案为 0！

证明：

::::info[加边数不会小于 max(S, T)] 如果小于，就会导致有的源点或者汇点走不到其他点。 ::::

::::info[存在一种构造方案，使得加边数等于 max(S, T)] 从汇点连到源点。不妨设 S \le T。因为如果 S > T，那么可以把边取反，转化成 S \le T，最后把添加的边也取反，就可以得到方案。

设源点集合为 P，汇点集合为 Q。

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

由于 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

割点

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

判断一个点是不是割点的条件：存在至少一个儿子 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]。

点双连通分量

割点同属于多个点双。

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

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

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);
}

注意：

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

矿场搭建

Redundant Paths G

嗅探器