第十二章 连通性问题

• 无向图的双连通性
  • 例1：P1656 炸铁路
  • 例2：P2860 [USACO06JAN]Redundant Paths G
• 无向图的点双连通性
  • 例3：P3388 【模板】割点（割顶）
  • 例4：P4630 [APIO2018] 铁人两项
• 有向图的强连通性
  • 例5：P2863 [USACO06JAN]The Cow Prom S
  • 例6：P3387 【模板】缩点
  • 例7：P4782 【模板】2-SAT 问题

在无向图中，连通性问题可以使用并查集解决。但是有一些点或者边是 “关键” 的，没有这些点或者边，这个图就会分裂成各个部分。

无向图中连通的点可以相互到达，有向图上的有序性是一个很好的性质，但对于多数错综复杂的有向图来说并不能直接进行拓扑排序。可以将一些可以互相到达的点合并成一个点，使这个有向图变为有向无环图，即可进行拓扑排序。

无向图的双连通性

例1：P1656 炸铁路

在无向图中，如果删去一条边后，图不连通了，这说明存在两个点 $u, v$，$u$ 到 $v$ 的路径必定经过这条边，那么把这条边叫做割边（或者桥）。如果一张图不存在割边，那么称这张图为边双连通图。一张图的极大双连通子图被称作边双连通分量。一张图的边双连通分量之间是不相交的：如果两个双连通分量相交了，那么删去其任意一条边，两个子图之间仍然连通。这说明了，点的 “属于同一个双连通分量” 的关系是带有传递性的。

对于边双连通还存在另一个等价定义：对于任意两点之间，存在至少两条边不相交的路径。

对于无向图，求出其所有双连通分量后，如果把每个双连通分量替换成一个点，那么剩下的是一颗树。这点在取出其生成树上也有体现：每一个双连通分量在生成树上都是一个连通块。

考虑树上连通快的性质：及其点集 $\text{DFS}$ 序最小为 $l$，最大为 $r$，那么其表示一个区间 $[l, r]$。将树分为若干个连通块后，所有的连通块之间代表的区间只有相离和包含两种关系。也就是可以像 $\text{DFS}$ 一样，用一个栈维护 $\text{DFS}$ 到的点，当一个点是连通块最浅的点时，弹出栈顶点一段区间就是弹出这个连通块。

有了这些性质，可以在一边 $\text{DFS}$ 中直接求出所有的边双连通分量：维护每个点是否是连通块深度最低的点，即通过树形 $\text{DP}$ 求出第 $i$ 个结点的子树，通过至多一条非树边能到的深度最低的点的 $\text{DFS}$ 序，也就是 $low_i$。需要注意的是，对于同一个图，遍历边的顺序不同，各点的 $dfn$ 和 $low$ 值也可能不同，但不影响求解答案。

遍历完一个子树，当发现 $low_v \gt dfn_u$，说明 $v$ 结点后续不会接回 $v$ 的祖先上，$(u, v)$ 就是一条割边。遍历完毕后，发现 $low_u = dfn_u$ 即子树没有非树边能到达自己的祖先的时候，就一直弹出栈的点，直到在栈中遇到自己为止，表示这些点属于同一个边双连通分量。

void addEBCC(int u) {
    ebcnt++;
    int v;
    do {
        v = s.top();
        s.pop();
        vertex[v].bel = ebcnt;
    } while (v != u);
}

void DFS(int u, int from) {
    dfn++;
    vertex[u].dfn = dfn;
    vertex[u].low = dfn;
    s.push(u);
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (v == from) continue;
        if (!vertex[v].dfn) {
            DFS(v, u);
            vertex[u].low = std::min(vertex[u].low, vertex[v].low);
            if (vertex[v].low > vertex[u].dfn) ans.push_back(std::make_pair(std::min(u, v), std::max(u, v)));
        } else {
            vertex[u].low = std::min(vertex[u].low, vertex[v].dfn);
        }
    }
    if (vertex[u].low == vertex[u].dfn) addEBCC(u);
    return;
}

例2：P2860 [USACO06JAN]Redundant Paths G

将所有边双连通分量看作一个点，那么得到的新图里的边全是原图的割边。也就是要加若干条边，使这些边覆盖的链的并是所有割边。一个容易猜到的结论是，将新图的叶子两两配对，那么当新图点数不为 $1$ 的时候，假设有 $k$ 个叶子，那么答案是 $\lceil \frac{k}{2} \rceil$。

所以统计叶子个数就得到了答案，算法的时间复杂度 $\mathcal O(n + m)$。

void addEBCC(int u) {
    ebcnt++;
    int v;
    do {
        v = s.top();
        s.pop();
        vertex[v].bel = ebcnt;
    } while (v != u);
    return;
}

void DFS(int u, int from) {
    dfn++;
    vertex[u].low = dfn;
    vertex[u].dfn = dfn;
    s.push(u);
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (v == from) continue;
        if (!vertex[v].dfn) {
            DFS(v, u);
            vertex[u].low = std::min(vertex[u].low, vertex[v].low);
        } else {
            vertex[u].low = std::min(vertex[u].low, vertex[v].dfn);
        }
    }
    if (vertex[u].low == vertex[u].dfn) addEBCC(u);
    return;
}

void mian() {
    for (int e1 = 1; e1 <= ecnt; e1 += 2) {
        int e2 = e1 + 1;
        int u = edge[e1].head;
        int v = edge[e2].head;
        if (vertex[u].bel != vertex[v].bel) {
            block[vertex[u].bel].degree++;
            block[vertex[v].bel].degree++;
        }
    }
    for (int b = 1; b <= bcnt; b++) if (block[b].degree == 1) ans++;
    ans = (ans + 1) / 2;
    std::cout << ans << '\n';
    return;
}

无向图的点双连通性

例3：P3388 【模板】割点（割顶）

对应着割边，定义割点为删去一个点以及其相邻的边后，使得图不连通的点。如果一张图不存在割点，那么称这张图为点双连通图。类似的，极大点双连通子图被称作点双连通分量。

对于点双连通还存在另一个等价定义：对于任意两点 $u, v$ 之间，存在至少两条点不相交（不包含 $u, v$）的路径。

如果两个点双连通分量的点交大于 $1$，则删去任意一点其交仍大于等于 $1$，且图连通，所以两个点双连通分量的交最大为 $1$。这说明一条边不可能同时属于两个点双连通分量，所以点双连通可以看作是边之间带有传递性的关系。同样可以通过生成树来得到一张图所有的点双连通分量，对于非树边相当于将一条链上所有的边合并到一个集合。这说明点双连通分量仍然是树上的一个连通块。

类似边双连通分量的变种 $\text{Tarjan}$ 算法，求双连通分量可以直接计算边的 $\text{DFS}$ 序。但是这些连通分量都是基于点点，所以修改 $\text{Tarjan}$ 算法：用一个点代表其通向父结点的边，每次处理完点双连通分量深度最低的边（$low_v = dfn_u$）或者处理完割边（$low_v \gt dfn_u$）时，代表找到一个点双连通分量。

统计每个点属于的点双连通分量的数量，如果一个点属于多个点双连通分量，那么它就是一个割点。

void addVBCC(int u) {
    vbcnt++;
    int v;
    do {
        v = s.top();
        s.pop();
        vertex[v].degree++;
    } while (v != u);
    return;
}

void DFS(int u, int from) {
    dfn++;
    vertex[u].low = dfn;
    vertex[u].dfn = dfn;
    s.push(u);
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (v == from) continue;
        if (!vertex[v].dfn) {
            DFS(v, u);
            vertex[u].low = std::min(vertex[u].low, vertex[v].low);
            if (vertex[v].low >= vertex[u].dfn) {
                s.push(u);
                addVBCC(v);
            }
        } else {
            vertex[u].low = std::min(vertex[u].low, vertex[v].dfn);
        }
    }
    return;
}

每个点连接着若干个不同的点双连通分量，同时每个点双连通分量包含着若干点，可以依次性质将图变为树形结构，其中将原图顶点成为圆点，代表着点双连通分量的点被称作方点，那么这样的树形结构被称作圆方树。由于其描述了点双连通的结构，因此圆方树是解决点相关路径问题的利器。

要建立圆方树，由于已经又了深度关系，只需更改找到点双连通分量时的代码。

void addBlockForest(int u) {
    bfcnt++;
    int v;
    do {
        v = s.top();
        s.pop();
        addEdge(n + bfcnt, v);
    } while (v != u);
    return;
}

            if (vertex[v].low >= vertex[u].dfn) {
                s.push(u);
                addBlockForest(v);
            }

例4：P4630 [APIO2018] 铁人两项

问题可以转化为枚举 $s, f$，计算 $s$ 到 $f$ 的不经过重复点的路径上有多少可能经过的点。

关于这个问题，可以转化到圆方树上，圆点的贡献为 $-1$，这样计算权值和刚好是可能经过的点树：因为题目要求去掉两个端点，那么用路径上的方点计算贡献时，路径上所有的圆点都被多算了一次，圆点 $-1$ 的权值刚好出去多余的贡献。

有向图的强连通性

例5：P2863 [USACO06JAN]The Cow Prom S

有向图中，定义强连通为两点之间可以互相到达，这与无向图连通的性质十分类似。当一张图任意两个点都强连通，那么称这张图为强连通图。因为如果 $u$ 能到 $v$，$v$ 能到 $w$ 就有 $u$ 能到 $w$，所以强连通具有传递性。如果把强连通的点归为一类的话，原图的点集就会被分为若干个不相交的子集，其中每个子集都是原图中的一个极大强连通子图，这样的子图被称作强连通分量。

很多有向图问题中需要求出强连通分量。把强连通分量替换为点的操作为缩点，即建立一个点数为强连通分量个数的新图，当一条边的两端属于不同的强连通分量，那么在新图上在强连通分量对应的点之间连边。缩点之后的图是一张有向无环图，因为如果不是则与原图取到的是 “极大强连通子图” 矛盾。

在得到每个点属于的强连通分量编号后，缩点十分容易解决。所以问题就是怎么求出一张图的所有强连通分量。

解法 $1$（$\text{Tarjan}$ 算法）：尝试在 $\text{DFS}$ 生成树上计算。得到有向图的 $\text{DFS}$ 生成树后，非树边是存在横叉边的。但是这些横叉边起点的 $\text{DFS}$ 序必定比终点大。

除了横叉边，对于不在 $\text{DFS}$ 生成树上的边，终点是起点祖先的边，被称为反祖边（也可称后向边）。起点是终点祖先的边被称作前向边。

容易发现，前向边 $(u, v)$ 对于可到达性的作用相当于树上 $u$ 到 $v$ 的链，所以在求强连通分量的时候，前向边是没有用的。

对于反祖边，而反祖边的意义恰好和在求边双连通分量的时候一样：将树上一条链的点全部合并到一个集合。

剩下的是要考虑横叉边的意义，因为所有横叉边都是 $\text{DFS}$ 序大的 $u$ 连向 $\text{DFS}$ 序小的点 $v$。对于其 $LCA(u, v) = l$，如果 $v$ 和 $l$ 在同一强连通分量里，那么横叉边会将 $u$ 到 $l$ 的链合并。容易发现，这些 $\text{DFS}$ 序大的点的强连通性依赖于 $\text{DFS}$ 序小的，而在 $\text{DFS}$ 过程中，横叉边的起点的 $\text{DFS}$ 序也是递增的，按这样的顺序合并正确性得以保证。

修改求边双连通分量的算法，为了横叉边方便的合并，考虑当横叉边的终点 $v$ 在栈中的时候，说明 $u, v$ 的最近公共祖先 $l$ 并不是 $v$ 所在的强连通分量深度最小的点。也就是说，淡化 “仅通过至多一条反祖边能到达的深度最小结点的 $\text{DFS}$ 序” 的意义，将 $low$ 数组当作辅助合并的标记。因为 $u$ 到 $l$ 的路径上除了 $l$，所有点的 $\text{DFS}$ 序都比 $v$ 大，所以可以直接用 $low_u$ 与 $dfn_v$ 去最小值合并到 $l$。

注意到在一张有向图中，$\text{DFS}$ 函数可能会被执行多次，这是因为选择 $\text{DFS}$ 生成树根的结点不一定能够到达图上所有的点。这样做强连通分量不会被漏找或多找，因为对于任意一个结点，其总能到达其所在强连通分量中所有的点。

在缩点以后的图中如果 $u$ 能到达 $v$，那么 $u$ 所代表的强连通分量编号一定大于 $v$。因为只有在 $u$ 代表的点访问完所有能到达的点后，$u$ 代表的强连通分量才会被标号。

void addSCC(int u) {
    scnt++;
    int v;
    do {
        v = s.top();
        s.pop();
        vertex[v].ins = false;
        vertex[v].bel = scnt;
        scc[scnt].size++;
    } while (v != u);
    return;
}

void Tarjan(int u) {
    dfn++;
    vertex[u].low = dfn;
    vertex[u].dfn = dfn;
    vertex[u].ins = true;
    s.push(u);
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (!vertex[v].dfn) {
            Tarjan(v);
            vertex[u].low = std::min(vertex[u].low, vertex[v].low);
        } else if (vertex[v].ins) {
            vertex[u].low = std::min(vertex[u].low, vertex[v].dfn);
        }
    }
    if (vertex[u].low == vertex[u].dfn) addSCC(u);
    return;
}

解法 $2$（$\text{Kosaraju}$ 算法）：考虑缩点后得到的 $\text{DAG}$，将点进行拓扑排序。如果不像 $\text{Tarjan}$ 算法一样，先找拓扑序较大的点代表的强连通分量，而是先找拓扑序较小的会怎么样呢？也就是在找连通块的时候，不能 $\text{DFS}$ 到拓扑序较大的点代表的强连通分量。这个性质与原图得到的性质相反，所以可以在找强连通分量的时候，在原图的反图（即将所有的有向边 $(u, v)$ 反向，变成 $(v, u)$）上遍历，并且在找到一个强连通分量后，将其在反图上删除。

这样按拓扑排序从小到大做，每次 $\text{DFS}$ 能得到恰好一个强连通分量。所以问题被转化为，找到一个恰当的顺序来遍历求强连通分量。

将目光放在 $\text{DFS}$ 生成树中，一个强连通分量标志性的点上，这个标志性的点就是生成树中深度最小的点，将其称为一个强连通分量的特殊点。考虑 $\text{Tarjan}$ 算法中，一个强连通分量与早被找到，其特殊点在遍历的过程中越早遍历完子树。而一个特殊点一定比其强连通分量内其他点更晚被 $\text{DFS}$ 完子树。这说明按 “$\text{DFS}$ 完子树的时间” 从晚到早，就刚好能得到刚才所说的 “恰当的顺序”。

所以算法过程就是：在求 $\text{DFS}$ 生成树的时候，维护一个栈，在每个点遍历出边后，将这个点加入栈，然后在遍历找强连通分量的时候，每次取出栈顶对应的结点，并从这个结点开始遍历找强连通分量。这么做成功规避了 $\text{Tarjan}$ 算法中更为繁琐的 $\text{DP}$ 过程，所以 $\text{Kosaraju}$ 算法的代码非常简洁。

void DFS(int u) {
    vertex[u].vis = true;
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (!vertex[v].vis) DFS(v);
    }
    s.push(u);
    return;
}

void Kosaraju(int u, int bel) {
    vertex[u].vis = true;
    vertex[u].bel = bel;
    scc[bel].size++;
    for (int e = vertex[u].daeh; e; e = egde[e].next) {
        int v = egde[e].head;
        if (!vertex[v].vis) Kosaraju(v, bel);
    }
    return;
}

上面代码是朴素的 $\mathcal O(n + m)$ 的复杂度。

注意到深度优先搜索的过程中，对于 $u$，只需要找到 $v$，使得有向边 $(u, v)$ 存在，且 $v$ 未被标记。如果对于每一个 $u$，存下集合 $g_u = \{ \vert (u, v) \in E \}$，即有向边 $(u, v)$ 存在，同时记录集合 $t$ 表示 $v$ 是否被标记删除，那么找到这个 $v$ 只需要取出 $g_u \cap t$ 的任意一个元素。而这些操作，都可以使用 $\text{bitset}$ 在 $\mathcal O(\frac{n}{w})$ 的时间复杂度内完成。也就是说，如果一张图比较稠密，则可以使用 $\text{bitset}$ 来加速求强连通分量的过程。其复杂度为 $\mathcal O(\frac{n^2}{2})$。

例6：P3387 【模板】缩点

因为强连通分量中的点可以互相到达，，所以强连通分量里任意一个点，其所有点的权值都能累加。

所以将强连通分量看作一个权值为其点集权值和的点。这样子源点就变成了一个 $\text{DAG}$。接着就可以在 $\text{DAG}$ 上动态规划获得答案了。

注意到如果按强连通分量得到的顺序早晚进行从小到大编号的话，那么就不用拓扑排序了：因为如果拓扑序小的强连通分量 $A$ 的 $\text{DP}$ 结果依赖于拓扑序大的强连通分量 $B$，那么 $A$ 一定比 $B$ 晚得到。所以在 $\text{Tarjan}$ 算法中，找到强连通分量时就可以进行动态规划了。

void addSCC(int u) {
    scnt++;
    int v;
    int res = 0;
    do {
        v = s.top();
        s.pop();
        vertex[v].ins = false;
        vertex[v].bel = scnt;
        res += a[v];
        for (int e = vertex[v].head; e; e = edge[e].next) {
            int w = edge[e].head;
            int s = vertex[w].bel;
            scc[scnt].res = std::max(scc[scnt].res, scc[s].res);
        }
    } while (v != u);
    scc[scnt].res += res;
    ans = std::max(ans, scc[scnt].res);
    return;
}

void Tarjan(int u) {
    dfn++;
    vertex[u].low = dfn;
    vertex[u].dfn = dfn;
    vertex[u].ins = true;
    s.push(u);
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (!vertex[v].dfn) {
            Tarjan(v);
            vertex[u].low = std::min(vertex[u].low, vertex[v].low);
        } else if (vertex[v].ins) {
            vertex[u].low = std::min(vertex[u].low, vertex[v].dfn);
        }
    }
    if (vertex[u].low == vertex[u].dfn) addSCC(u);
    return;
}

例7：P4782 【模板】2-SAT 问题

$\text{2-SAT}$ 问题的标志就是每个变量只有 $01$ 取值，并且条件是 $A \Rightarrow B$ 这种形式。

于是可以将每个变量拆成两个点 $p_{i, 0}, p_{i, 1}$ 表示两种取值，用有向边 $A \rightarrow B$ 表示 $A \Rightarrow B$ 这种形式，同时加入每个命题的逆否命题，就能通过计算一个点能够到达的所有点来表示一个取值能推导出的其他所有变量。

如果 $A$ 和 $\neg A$ 属于同一个强连通分量，则必定是无解的。如果不存在这样的情况，则给出用 $\text{Tarjan}$ 算法得到的一种构造方法：对于每个变量取对应点所在强连通分量编号较小的值。

void addSCC(int u) {
    scnt++;
    int v;
    do {
        v = s.top();
        s.pop();
        vertex[v].ins = false;
        vertex[v].bel = scnt;
    } while (v != u);
    return;
}

void Tarjan(int u) {
    dfn++;
    vertex[u].low = dfn;
    vertex[u].dfn = dfn;
    vertex[u].ins = true;
    s.push(u);
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        if (!vertex[v].dfn) {
            Tarjan(v);
            vertex[u].low = std::min(vertex[u].low, vertex[v].low);
        } else if (vertex[v].ins) {
            vertex[u].low = std::min(vertex[u].low, vertex[v].dfn);
        }
    }
    if (vertex[u].low == vertex[u].dfn) addSCC(u);
    return;
}

    for (int i = 1; i <= n; i++) {
        sat[i][0] = ++vcnt;
        sat[i][1] = ++vcnt;
    }
    for (int k = 1; k <= m; k++) {
        std::cin >> i >> a >> j >> b;
        graph::addEdge(graph::sat[i][!a], graph::sat[j][b]);
        graph::addEdge(graph::sat[j][!b], graph::sat[i][a]);
    }
    for (int i = 1; i <= n * 2; i++) if (!graph::vertex[i].dfn) graph::Tarjan(i);
    for (int i = 1; i <= n; i++) {
        if (graph::vertex[graph::sat[i][0]].bel == graph::vertex[graph::sat[i][1]].bel) {
            std::cout << "IMPOSSIBLE" << '\n';
            return 0;
        }
    }
    std::cout << "POSSIBLE" << '\n';
    for (int i = 1; i <= n; i++) {
        if (graph::vertex[graph::sat[i][0]].bel < graph::vertex[graph::sat[i][1]].bel) std::cout << 0 << ' ';
        else std::cout << 1 << ' ';
    }