强联通分量

Tarjan

模版

C++
struct Graph {
    int n, tot, pcnt;
    vector<vector<int>> adj, nadj, na;
    vector<int> dfn, low, bel;
    vector<bool> in;
    stack<int> st;
    Graph(int n) : n(n), adj(n + 1), in(n + 1), dfn(n + 1), low(n + 1), bel(n + 1), tot(0), pcnt(0) { }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++tot;
        st.push(u);
        in[u] = true;
        for (auto &to : adj[u]) {
            if (!dfn[to]) {
                tarjan(to);
                low[u] = min(low[u], low[to]);
            } else if (in[to]) {
                low[u] = min(low[u], dfn[to]);
            }
        }
        if (low[u] == dfn[u]) {
            pcnt++;
            while (true) {
                int x = st.top();
                st.pop();
                in[x] = false;
                bel[x] = pcnt;
                if (u == x) {
                    break;
                }
            }
        }
    }
    void scc() {
        for (int i = 1 ; i <= n ; i++) {
            if (!dfn[i]) {
                tarjan(i);
            }
        }
        nadj.resize(pcnt + 1);
        na.resize(pcnt + 1);
        for (int i = 1 ; i <= n ; i++) {
            na[bel[i]].push_back(i);
            for (auto &to : adj[i]) {
                if (bel[i] == bel[to]) continue;
                nadj[bel[i]].push_back(bel[to]);
            }
        }
    }
}; // Graph
// 定义 Graph g(n) 表示一个 n 个点的有向图
// 使用 g.addEdge(u, v) 进行添加有向边 (u, v)
// 使用 g.scc() 即可进行缩点

例题

洛谷P3387洛谷P3609

P3387 【模板】缩点 - 洛谷

C++
int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    vector<int> a(n + 1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }
    g.scc(); // 缩点后建反向边
    int pcnt = g.pcnt;
    auto adj = g.nadj;
    vector<int> b(pcnt + 1), deg(pcnt + 1), dist(pcnt + 1);
    for (int i = 1;  i <= n ; i++) {
        b[g.bel[i]] += a[i];
    }
    for (int i = 1 ; i <= pcnt ; i++) {
        for (auto &to : adj[i]) {
            deg[to]++;
        }
    }
    queue<int> que;
    for (int i = 1 ; i <= pcnt ; i++) {
        dist[i] = b[i];
        if (deg[i] == 0) {
            que.push(i);
        }
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto &to : adj[u]) {
            dist[to] = max(dist[to], dist[u] + b[to]);
            if (deg[to]-- == 1) {
                que.push(to);
            }
        }
    }
    int ans = 0;
    for (int i = 1 ; i <= pcnt ; i++) {
        ans = max(ans, dist[i]);
    }
    cout << ans;
    return 0;
}

B3609 [图论与代数结构 701] 强连通分量 - 洛谷

C++
int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }
    g.scc();
    cout << g.pcnt << "\n";
    vector<bool> vis(n + 1);
    for (int i = 1 ; i <= n ; i++) {
        int bel = g.bel[i];
        if (vis[bel]) continue;
        vis[bel] = true;
        for (auto &x : g.na[bel]) {
            cout << x << " ";
        }
        cout << "\n";
    }
    return 0;
}

习题

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G - 洛谷

\(n\) 个点, \(m\) 条有向边。

问能被所有点到达的点有多少个？

缩点后，统计出度，只有出度为 \(0\) 的点才可能被所有点到达，如果有多个，则一定不能被所有点到达。

C++
int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }
    g.scc();
    int pcnt = g.pcnt;
    vector<int> deg(pcnt + 1);
    auto adj = g.nadj;
    for (int i = 1 ; i <= pcnt ; i++) {
        deg[i] += adj[i].size();
    }
    int cnt = 0, ans = 0;
    for (int i = 1 ; i <= pcnt ; i++) {
        if (deg[i] == 0) {
            cnt++;
            ans = g.na[i].size();
        }
    }
    if (cnt > 1) ans = 0;
    cout << ans;
    return 0;
}