题解 P3387 【模板】缩点 | Kosaraju 学习笔记

Mr_罗 · 2024-12-05 20:28:25 · 题解

TL;DR：Kosaraju

翻了一圈题解，只有 this 使用了 Kosaraju 算法，然而 TA 既不知道这个算法叫做 Kosaraju 又没有详解，特此写一篇题解，顺便当作学习笔记。

P.S. Kosaraju 不是一个日本名，大概率是印度名（？）

介绍

问题 给定一张图 G(V,E)，求其所有连通分量。

做法

• 对于边集 E，记 E^{\sf R}=\{(v,u)\mid (u,v)\in E\}；对于图 G，记 G^{\sf R}=(V,E^{\sf R})（即反图）。
• 首先 dfs 图 G，求每个点 结束访问 的顺序（若第一次未遍历完则取后面未被遍历的点接着遍历，就像 Tarjan 一样）。
• 接着按照 结束访问顺序 倒序 取点 u：
  • 若 u 未标记，则在 反图 \boldsymbol{G^{\sf R}} 上将所有 u 能够走到的未标记结点标记为在一个新的强连通分量中。

现在你获得了 G 的所有 SCC。

优势：代码好写。

劣势：常数稍大。

代码

证明 在下面。

拓扑部分自己写或借鉴其他题解。

int n, m, ans;
int a[N];
vi G[N], H[N];
bool vs[N];
int bl[N], tt;
vi sc[N], pt;
int qu[N], lh, rt;
int ds[N];

void dfs1(int u) {
    vs[u] = 1;
    for (auto v : G[u]) if (!vs[v]) dfs1(v);
    pt.eb(u);
}

void dfs2(int u) {
    sc[bl[u] = tt].eb(u);
    for (auto v : H[u]) if (!bl[v]) dfs2(v);
}

void mslv() { // main solve
    scanf("%d%d", &n, &m);
    rep(i, 1, n) scanf("%d", a + i);
    rep(i, 1, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].eb(v), H[v].eb(u);
    }
    rep(u, 1, n) if (!vs[u]) dfs1(u);
    for (reverse(all(pt)); auto u : pt)
        if (!bl[u]) tt++, dfs2(u);
    // 共 tt 个 SCC，每个 SCC 中的点记录在 sc[i] 中
    // 每个点属于的 SCC 的编号在 bl[u] 中
    bld(), topo(); // 不贴了
    printf("%d\n", ans);
}

证明

定理 G^{\sf R} 与 G 的强连通分量构成的集合完全相同。
即：SCC 个数相同，每个 SCC 包含的结点也相同。

证明 显然一个环反向之后还是环，而那些不成环的边反向之后依然不成环。\square

不会严谨 证明，感性理解一下。

考虑缩完点的图，对于一个 SCC k，只需要拓扑序比它小的点中访问结束最晚的点结束比自己所有点都晚就好了：经过简单的分讨验证，这是成立的。\triangle

闲话

下面是我原来写的 证明 ：

`dfs1` 结束后你获得了一个遍历顺序，感受一下反转后的序列：

- 分成若干片场，每个片场包含若干完整的 SCC（dfs 不可能把 SCC 切开，但 SCC 不一定连续）。
- 不同次在主函数调用 `dfs1` 中越先调用越靠后
- 对于一个片场（不妨考虑 $1$ 号点可以走到所有点，此时只有一个片场），$1$ 号点所在 SCC 中一部分点早早结束访问（例如走环碰见 $1$ 号点就滚粗了），另一部分顺着其他 SCC 溜走了，在它们访问完后才结束访问。**此时 $1$ 号点最晚结束。**

看看 `dfs2`：

- 倒序取点最先取到 $1$ 号点，假设原图中 $1$ 可以走到任何点（即 $1$ 所在 SCC 是缩点后 DAG 唯一入度为 $0$ 的点），那么反图中 $1$ 所有能走到的点只能是它所在的 SCC 了。
- 若有其他点能走到 $1$ 且不在同一个 SCC 中，那么那个点肯定片场靠后，倒序后靠前，比 $1$ 先取。
- 若有点和 $1$ 在原图中互相不可达（$1\to2\gets3$），那么显然顺序无关紧要。
- 考虑一个缩完点之后有入边的 SCC $k$，若只有一个 SCC 和 $k$ 有指向 $k$ 的边，那么显然 $k$ 访问结束后该 SCC 中的点才会访问完毕，倒序后还是缩点后拓扑序更小的会先 `dfs2`；若有多个，由于 dfs 先到先得，那么另外的那些可以直接走到 $k$ 的 SCC 肯定会更晚。

wtcl :(