(图论) 连通分量(模板) + 强连通分量(模板)

文章目录

前言
- 模板题介绍
连通分量
强连通分量
- tarjan 算法
- kosaraju 算法
END

前言

连通分量_百度百科强连通分量_百度百科

图的联通性是图论中的基础问题之一。

无向图的连通分量通常比较好实现，直接搜索即可。通常方法有：并查集，DFS，BFS

而有向图的强分量的实现与计算则比较困难。通常方法有：tarjan kosaraju

本文不从0开始讲解思路和代码，以展示模板为主，当然强联通分量的算法也可以直接应用于连通分量中

模板题介绍

练习题：

无向图连通分量

力扣：6106. 统计无向图中无法互相到达点对数

有向图强连通分量

洛谷：P3387 【模板】缩点

6106. 统计无向图中无法互相到达点对数

本题是求连通分量的裸题，目的是计算每个联通分量的点的个数

最后求解无法互相到达的点对的对数

注意：[0,1] 和 [1,0]视为一对，因此在最后计算时候要➗2

统计总数时有两种方式

总对数 - 可到达点对数
sum不可到达点对数

本文的代码均用第二种方法

P3387 【模板】缩点

本题并不是求强联通分量的裸题，还要会根据求得的强连通分量进行缩点

根据强连通分量进行缩点

重新建图
重新设置代表点的点权
跑新图搜索答案

连通分量

并查集

并查集天然的能处理无向图的联通性

根据路劲压缩的find就能找到该点的代表点

若对并查集非常熟悉的话，可以在合并的时候一起叠加点数

class UnionFind {
private:
    bool flag;              // false[0~n-1], true[1~n]
    int n;
    vector<int> parent;

public:
    UnionFind(int n, bool flag = false):n(n), parent(n), flag(flag) {
        iota(parent.begin(), parent.end(), 0);
        if (flag) {
            parent.push_back(n);
        }
    }

    int find(int x) {   // 记忆化，路径压缩
        return x == parent[x] ? x : parent[x] = find(parent[x]);
    }

    void unite(int x, int y) {  // x合并到y中
        parent[find(x)] = find(y);
    }

    int getSccCnt() {   // 统计图中有多少个联通分量
        int cnt = 0;
        for (int i = flag; i < n + flag; i++) {
            cnt += (i == parent[i]);
        }
        return cnt;
    }
};

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        UnionFind uf(n);

        for (auto& arr : edges) {
            uf.unite(arr[0], arr[1]);
        }

        unordered_map<int ,int> ump;
        for (int i = 0; i < n; i++) {
            ++ump[uf.find(i)];
        }

        long long sum = 0;
        for (auto& [key, val] : ump) {
            sum += 1LL * val * (n - val);
        }

        return sum / 2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

DFS

常规搜索，这里用scc[] 顺便代替了vis[]的作用

从AC本题的角度来说，可以在每个搜索中记录遍历的点数，减少后面的统计scc[]的步骤，但是还是得有vis[]的标记

class Solution {
private:
    vector<vector<int>> graph;  // 无向图
    vector<int> scc;            // 联通分量，顺便记录vis

    void init(int n) {
        this->graph.resize(n);
        this->scc.resize(n, -1);
    }

    void dfs(int cur, int top) {
        if (scc[cur] != -1) {
            return;
        }
        scc[cur] = top;
        for (int& nex : graph[cur]) {
            dfs(nex, top);
        }
    }

public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        init(n);

        // 建立无向图
        for (auto& arr : edges) {
            graph[arr[0]].emplace_back(arr[1]);
            graph[arr[1]].emplace_back(arr[0]);
        }

        for (int i = 0; i < n; i++) {
            if (scc[i] == -1) {
                dfs(i, i);
            }
        }

        unordered_map<int, int> ump;
        for (int i = 0; i < n; i++) {
            ++ump[scc[i]];
        }

        long long sum = 0;
        for (auto& [key, val] : ump) {
            sum += 1LL * val * (n - val);
        }

        return sum / 2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

BFS

同DFS一样

class Solution {
private:
    vector<vector<int>> graph;  // 无向图
    vector<int> scc;            // 联通分量，顺便记录vis

    void init(int n) {
        this->graph.resize(n);
        this->scc.resize(n, -1);
    }

    void bfs(int start, int top) {
        queue<int> q;
        q.push(start);
        scc[start] = top;

        while (!q.empty()) {
            auto cur = q.front();
            q.pop();

            for (int& nex : graph[cur]) {
                if (scc[nex] == -1) {
                    scc[nex] = top;
                    q.push(nex);
                }
            }
        }
    }

public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        init(n);

        // 建立无向图
        for (auto& arr : edges) {
            graph[arr[0]].emplace_back(arr[1]);
            graph[arr[1]].emplace_back(arr[0]);
        }

        for (int i = 0; i < n; i++) {
            if (scc[i] == -1) {
                bfs(i, i);
            }
        }

        unordered_map<int, int> ump;
        for (int i = 0; i < n; i++) {
            ++ump[scc[i]];
        }

        long long sum = 0;
        for (auto& [key, val] : ump) {
            sum += 1LL * val * (n - val);
        }

        return sum / 2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

强连通分量

专题：(图论) Tarjan 算法_天赐细莲的博客-CSDN博客

tarjan 算法

思想：

在递归站中的low值相等的点是一个强联通分量

dfn值和low值相等的是该分量的代表点

/**
 * https://www.luogu.com.cn/problem/P3387
 * P3387 【模板】缩点
 *
 * tarjan 求强连通分量
 * 然后缩点构造DAG图
 */
#include <bits/stdc++.h>
#define int long long
using namespace std;

// tarjan 标配
vector<vector<int>> graph;  // 存图
vector<int> dfn;            // dfs被访问的时间点
vector<int> low;            // 通过回溯可以到达的最早时间点
int timestamp = 1;          // 时间戳
// 求强连通分量 标配
vector<int> scc;     // 强联通分量
stack<int> stk;      // 递归栈
vector<bool> inStk;  // 快速辨别是都在递归栈中

void tarjan(int cur) {
    dfn[cur] = low[cur] = timestamp++;
    stk.push(cur);
    inStk[cur] = true;

    for (int& nex : graph[cur]) {
        if (dfn[nex] == 0) {
            // 未访问则搜索一次
            tarjan(nex);
            low[cur] = min(low[cur], low[nex]);
        } else if (inStk[nex]) {
            // 在栈中，也要松弛一次
            low[cur] = min(low[cur], dfn[nex]);
        }
    }

    // 自己的dfn和low相同，则构成一个强联通分量
    if (dfn[cur] == low[cur]) {
        int x = -1;
        do {
            x = stk.top();
            stk.pop();
            inStk[x] = false;
            scc[x] = cur;
        } while (x != cur);
    }
}

signed main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n + 1);
    dfn.resize(n + 1);
    low.resize(n + 1);
    timestamp = 1;
    scc.resize(n + 1, -1);
    inStk.resize(n + 1);

    vector<int> val(n + 1);   // 点权
    vector<int> from(m + 1);  // 出发点
    vector<int> to(m + 1);    // 到达点

    // 点权
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    // 建图，单向图
    for (int i = 1; i <= m; i++) {
        cin >> from[i] >> to[i];
        graph[from[i]].emplace_back(to[i]);
    }

    // 跑tarjan 获得强连通分量
    for (int i = 1; i <= n; i++) {
        if (dfn[i] == 0) {
            tarjan(i);
        }
    }

    /** ******** tarjan 跑完，获得强连通分量 ****************************/
    /** ******** 根据强连通分量，缩点构造DAG图 ***************************/

    // 先将每个强联通分量的点权集中到代表点上
    for (int i = 1; i <= n; i++) {
        if (scc[i] != i) {  // 代表点不用重复加
            val[scc[i]] += val[i];
        }
    }

    unordered_map<int, vector<int>> dagGraph;
    for (int i = 1; i <= m; i++) {
        int &u = from[i], &v = to[i];
        // 不在一个分量中
        if (scc[u] != scc[v]) {
            dagGraph[scc[u]].emplace_back(scc[v]);
        }
    }

    function<int(int)> dfsDag = [&](int cur) -> int {
        int sum = 0;
        for (int& nex : dagGraph[cur]) {
            // 获得子树的最大值，还可以记忆化优化下
            sum = max(sum, dfsDag(nex));
        }
        return val[cur] + sum;
    };

    int maxx = 0;
    // 遍历每个点，可能有某点的是单独的分量没有边
    for (int i = 1; i <= n; i++) {
        if (scc[i] == i) {
            maxx = max(maxx, dfsDag(scc[i]));
        }
    }

    cout << maxx << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

kosaraju 算法

另一种求强连通分量的方法

建立正向和反向图
先dfs反向图
在正向图中逆序dfs反向图的结果，并记录每个点在哪个联通分量中

/**
 * https://www.luogu.com.cn/problem/P3387
 * P3387 【模板】缩点
 *
 * kosaraju 求强连通分量
 * 然后缩点构造DAG图
 */
#include <bits/stdc++.h>
#define int long long
using namespace std;

// kosaraju 标配
vector<vector<int>> forwardGraph;  // 正向图
vector<vector<int>> reverseGraph;  // 反向图
vector<int> scc;                   // 强连通分量
vector<int> vis;                   // vis标记
stack<int> stk;                    // 反图入栈

void reverseDFS(int cur) {
    vis[cur] = true;
    for (int& nex : reverseGraph[cur]) {
        if (!vis[nex]) {
            reverseDFS(nex);
        }
    }
    // 访问的点依次入栈
    stk.push(cur);
}

void forwardDFS(int cur, int father) {
    vis[cur] = true;
    scc[cur] = father;  // 记录是哪个强连通分量
    for (int& nex : forwardGraph[cur]) {
        if (!vis[nex]) {
            forwardDFS(nex, father);
        }
    }
}

signed main() {
    int n, m;
    cin >> n >> m;

    forwardGraph.resize(n + 1);
    reverseGraph.resize(n + 1);
    scc.resize(n + 1);
    vis.resize(n + 1);

    vector<int> val(n + 1);   // 点权
    vector<int> from(m + 1);  // 出发点
    vector<int> to(m + 1);    // 到达点

    // 记录点权
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

    // 正向反向图同时建立
    for (int i = 1; i <= m; i++) {
        cin >> from[i] >> to[i];
        forwardGraph[from[i]].push_back(to[i]);
        reverseGraph[to[i]].push_back(from[i]);
    }

    fill(vis.begin(), vis.end(), false);
    // 反向图遍历
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            reverseDFS(i);
        }
    }
    fill(vis.begin(), vis.end(), false);
    // 逆序遍历反向图的结果
    // 目的是获得强连通分量scc
    while (!stk.empty()) {
        int cur = stk.top();
        stk.pop();
        if (!vis[cur]) {
            forwardDFS(cur, cur);
        }
    }

    /** ************** kosaraju 跑完，获得强连通分量 *********************/
    /** ******** 根据强连通分量，缩点构造DAG图 ***************************/

    // 先将每个强联通分量的点权集中到代表点上
    for (int i = 1; i <= n; i++) {
        if (scc[i] != i) {  // 代表点不用重复加
            val[scc[i]] += val[i];
        }
    }

    unordered_map<int, vector<int>> dagGraph;
    for (int i = 1; i <= m; i++) {
        int &u = from[i], &v = to[i];
        // 不在一个分量中
        if (scc[u] != scc[v]) {
            dagGraph[scc[u]].emplace_back(scc[v]);
        }
    }

    function<int(int)> dfsDag = [&](int cur) -> int {
        int sum = 0;
        for (int& nex : dagGraph[cur]) {
            // 获得子树的最大值，还可以记忆化优化下
            sum = max(sum, dfsDag(nex));
        }
        return val[cur] + sum;
    };

    int maxx = 0;
    // 遍历每个点，可能有某点的是单独的分量没有边
    for (int i = 1; i <= n; i++) {
        if (scc[i] == i) {
            maxx = max(maxx, dfsDag(scc[i]));
        }
    }

    cout << maxx << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

END

相关阅读:
关于dubbo的rpc基于传输层一说
 MySQL数据库——索引（6）-索引使用（覆盖索引与回表查询，前缀索引，单列索引与联合索引）、索引设计原则、索引总结
 C++中float和double的比较
 numpy.hstack
CSS移动端适配方案
 Abp Quartz配置Sqlite
# get请求和post请求的区别
 自动对话系统
 old version wakelock.h
【微服务】微服务学习笔记二：Eureka注册中心的介绍及搭建
原文地址：https://blog.csdn.net/CUBE_lotus/article/details/125475905