强连通分量 - 割点桥 - 双缩点

无向图连通分量：

$dfs$ 即可。

有向图强连通分量:

$dfs$ 中记录每个结点能到达的最前祖先，并入栈；若某个结点有 $dfn_u=pre_u$ ，则当前栈顶到 $u$ 是一个强连通分量。

缩点：

有些一般图的问题可以把一个强连通分量视作一个点，

然后转换成 $DAG$ 上的问题，就可以用拓扑排序解决。

注意，缩点后需要对每个得到的强连通分量重新加边。

例题：

#10093. 「一本通 3.5 练习 1」网络协议

第一问只需缩点后求入度为 $0$ 点个数即可。

第二问稍有意思。

缩点后，第二问即问向一个 $DAG$ 中加多少边可使其强连通。

情况1：如果只有一个点，那么图已经强连通， $Answer = 0$ 。

情况2：

否则设图中入度为 $0$ 的点有 $a$ 个，出度为 $0$ 的点有 $b$ 个，则 $Answer \geq max(a, b)$ 。

这是因为：不妨设 $a \leq b$ 。则每个出度为 $0$ 的点都要能相互到达，至少需要 $b$ 条边。

然后我们可以给出一个用 $max(a, b)$ 条边满足要求的例子，即 $Answer \leq max(a, b)$ 可取到等号，那么答案就是 $max(a,b)$ 。

此技巧解组合数学题常用。

构造方法即为对每一个出度为 0 的向入度为 0 的点连边，

并保证每个入度为 0 的点都被出度为 0 的点相连。

至于孤立点，从其引一条边到入（出）度为 0 的点，则这个孤立点成为新的入（出）度为 0 的点。

#10096. 「一本通 3.5 练习 4」抢掠计划

缩点求给定起点到某些可以结束点的最长路。

有个坑：缩点只能从缩起点可达的点。不然会导致拓扑的过程中有些起点到不了的点不被访问，因而它连的点入度不能变成 $0$ ，就不能被加进队列。

无向图的割点和桥

割点是指去掉这个点，图的连通块数量会 $++$ 的点，

而桥指去掉这个边，图的连通块数量会 $++$ 的边。

如果我们用 $pre[u]$ 表示 $u$ 所能到达的 $dfs$ 序最小的祖先，那么

$u$ 是割点 $\iff$ 存在 $u$ 的儿子 $v, pre[v] \geq pre[u]$

$u$ 到儿子 $v$ 的边是桥 $\iff$ $pre[v] > pre[u]$

注意：根节点是割点的条件是儿子数大于 $1$ 。

这里写代码的时候有个注意点：

        if(!dfn[v])
    {
            child ++;
        dfs(v, u);
        pre[u] = min(pre[u], pre[v]);
            if(pre[v] > dfn[u]) isbrige[i] = isbrige[i ^ 1] = true;
            if(pre[v] >= dfn[u] && fa != 0) iscut[u] = true;
    }    
    else if(v != fa)
            pre[u] = min(pre[u], dfn[v]);//这里不能用 pre[v] 代替 dfn[v]。

原因：

由于此处是一张无向图，我们又双向建了边，导致节点可以回溯到它的父节点；

而如果从它的父节点或其父节点的另一棵子树上有向上很多的返祖边，

这时把子节点的 $low$ 值赋为父节点的 $low$ ，就可能导致其 $low==$ 其父节点 $low<$ 其父节点 $dfn$ ，

从而使本该是割点的点被忽视了。

例题

#10101. 「一本通 3.6 练习 2」嗅探器

求给定两点路径中的关键点。

关键点显然是割点。

我们从起点开始 $dfs$ ，遇到一个割点，就判断 $pre[ed]$ 是否 $\geq dfn[u]$ ，如果满足，那么 $u$ 就是一个关键点。

#10103. 「一本通 3.6 练习 4」电力

求一个图删除一个点之后，联通块最多有多少。

对于每个割点，记录它被删除后会多出多少连通块即可。

对于根节点，多出的就是 $child - 1$ ；

对于非根节点，多出的就是满足 $pre[v] \geq pre[u]$ 的儿子数。

小坑：图中可能没有割点，此时如果没有边，答案就是 $n - 1$ ，如果有边，答案就是 $n$ 。

#10104. 「一本通 3.6 练习 5」Blockade

求去掉一个点后有多少对点不可达。

如果去掉 $u$ 是根，若其有儿子，儿子树大小 $a, b, c$ , 则答案为 $(n - 1) * 2 + 2ab + 2bc + 2ca = n^2 - a^2-b^2-c^2-1$

如果去掉 $u$ 不是根，设其有若干儿子，例如二个儿子，儿子树大小 $a, b$ 不能通过非树边到达 $u$ 的祖先，那么这二个儿子，与其他儿子和 $u$ 祖先这三个团两两不可达，答案是 $2 * (n - 1) + 2ab + 2bfasiz + 2afasiz = n^2 - a^2 - b^2 - fasiz^2 - 1$