强连通分量 – 缩点

Coding, OI 0 Comments

这篇文章咕了两个月。感谢 @rickyxrc 的催更。

如果你还不知道什么是强连通分量的话，参见我本系列的上一篇文章：强连通分量 – Kosaraju Algorithm

引入

强连通分量的缩点，就是把图上的每一个强连通分量都视作一个点（或者更通俗的，缩成一个点）。SCC 与 SCC 之间的边连接依然参照原图保留。

缩点解决了部分算法「跑不了环」的问题，比如拓扑排序。并且对于部分题目，缩点之后的图对于原图来说没有太大的区别。

图示

如图所示，1 2 3 和 4 5 6 分别属于两个 SCC。把 1 2 3 看作新的点 1，4 5 6 看作新的点 2，那么上图可以缩成：

简单吧？

（机械化的）思路

根据 强连通分量 – Kosaraju Algorithm 的板子，我们存了每一个点对应的 SCC 编号。因此，跑完 SCC 算法之后，遍历原图的每一条边，然后再新的图上的 SCC 建立与之对应的边。

语文不好可能有点绕

代码

还是代码比我说的话好理解啊。

核心部分代码如下（P3387 【模板】缩点）：

// main
g.run_tarjan(n);
for (int i = 1; i <= n; i++) {
    for (auto x: g.graph[i]) {
        // 判断两个点是否在一个 SCC 里 在同一个 SCC 就不需要自己建边
        // 要不然有自环
        if (g.SCC[i] != g.SCC[x]) {
            // 在新的图里建边
            new_graph[g.SCC[i]].push_back(g.SCC[x]);
            // 加入度
            ++in_degree[g.SCC[x]];
        }
    }
    // 缩点权
    new_weight[g.SCC[i]] += weight[i];
}

练习题