2-3 个月强化训练阶段：图论算法之强连通分量缩点

在 CSP-S 备考的 2 - 3 个月强化训练阶段，图论算法中的强连通分量缩点是一个重要的知识点。

一、强连通分量的概念

强连通分量是指在一个有向图中，任意两个顶点之间都存在路径。也就是说，从任意一个顶点出发都能到达其他所有顶点。

二、缩点的目的

缩点的主要目的是将一个复杂的图简化，把每个强连通分量看成一个点，从而形成一个新的有向无环图（DAG）。

三、缩点后 DAG 的构建过程

（一）去除自环
在原图中，如果存在顶点指向自身的边，在缩点时需要将这些自环去除。因为缩点后的图每个点代表一个强连通分量，自环没有实际意义。

（二）合并多重边
如果在原图中，两个强连通分量之间存在多条边，在缩点后的图中只保留一条即可。

四、在缩点后的图上求解连通性问题

比如判断是否存在一条路径经过所有缩点。这可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。从任意一个入度为 0 的缩点开始，依次访问其相邻的缩点，如果最终能够访问到所有缩点，则存在这样的路径；否则，不存在。

五、缩点操作的代码实现

以下是一个简单的示例代码：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> graph;
vector<int> dfn, low, belong;
vector<bool> in_stack;
stack<int> s;
int index, scc_count;

void tarjan(int u) {
    dfn[u] = low[u] = ++index;
    s.push(u);
    in_stack[u] = true;

    for (int v : graph[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++scc_count;
        int v;
        do {
            v = s.top();
            s.pop();
            in_stack[v] = false;
            belong[v] = scc_count;
        } while (v!= u);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n + 1);
    dfn.resize(n + 1, 0);
    low.resize(n + 1, 0);
    belong.resize(n + 1, 0);
    in_stack.resize(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // 缩点后的图构建及相关操作
    // ...

    return 0;
}

总之，掌握强连通分量缩点对于解决图论中的复杂问题至关重要，希望大家通过不断的练习和总结，能够熟练运用这一知识点，在 CSP-S 考试中取得好成绩。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！