【每日一题】统计无向图中无法互相到达点对数

Tag

【DFS+乘法原理】【并查集】【图】【数组】【2023-10-21】

---

题目来源

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

---

题目解读

节点之间的连接关系是通过数组给出的，n 个节点构成了一幅有向图，你需要统计出有向图中无法相互到达的点对数目。

---

解题思路

一个朴素的想法是根据数组将有联系的节点连接起来记作一个二维数组 links，那么 links[i][j] 的值表示的就是节点 i 和 j 之间的连通情况，值为 1 表示两个节点之间可以相互到达，值为 0 表示两个节点之间无法相互到达。 然后枚举所有的点对，根据 links 的值判断枚举的点对之间是否可以相互到达，进而更新无向图中无法相互到达的点对数。

该方法首先需要判断任意两个节点之间是否连通，可以通过并查集来解决，该方法将在 方法一：并查集 中进行介绍，也可以通过 DFS 来解决，该方法将在 方法二：DFS+乘法原理 中解决。

但是在枚举所有的点对的时间复杂度为 $O(n^2)$，对于数据规模为 $10^5$ 的题目，该解法一定超时。于是我们需要优化时间复杂度。

因为需要统计无向图点对之间的连通情况，因此必须要解决连通量问题。然后在计数上想办法优化时间。

方法一：并查集

我们使用并查集来解决节点之间的连通，关于并查集的知识，可以参考 【并查集（上）基础篇】 、【并查集（下）应用篇】 这两篇文章。

我们维护一个数组 sizes，sizes[i] 表示节点 i 所在的连通分量的节点数（这个数组我们在合并两个节点的时候更新），n - size[i] 表示的就是与节点 i 不能互相到达的节点数。对每个节点进行这样的计算后求和，但这样的方法计算，每个点对会被计算两次，因此最后结果需要除以 2。

实现代码

class UnionFind {
private:
    vector<int> parents;
    vector<int> sizes;
public:
    UnionFind(int n) : parents(n), sizes(n, 1) {
        iota(parents.begin(), parents.end(), 0);
    }
    int Find(int x) {
        if (parents[x] == x) {
            return x;
        }
        return parents[x] = Find(parents[x]);
    }
    void Union(int x, int y) {
        int rx = Find(x), ry = Find(y);
        if (rx != ry) {
            if (sizes[rx] > sizes[ry]) {
                parents[ry] = rx;
                sizes[rx] += sizes[ry];
            } else {
                parents[rx] = ry;
                sizes[ry] += sizes[rx];
            }
        }
    }
    int GetSize(int x) {
        return sizes[x];
    }
};

class Solution {
public:
    long long countPairs(int n, vector<vector<int>> &edges) {
        UnionFind uf(n);
        for (const auto &edge : edges) {
            uf.Union(edge[0], edge[1]);
        }
        long long res = 0;
        for (int i = 0; i < n; i++) {
            res += n - uf.GetSize(uf.Find(i));
        }
        return res / 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

复杂度分析

时间复杂度：$O((m+n)\times \alpha (n))$，其中 $m$ 是边数，$\alpha$ 表示阿克曼函数的反函数。

空间复杂度：$O(n)$。

以上的实现代码与复杂度分析参考自 统计无向图中无法互相到达点对数。

方法二：DFS+乘法原理

连通分量还可以通过深度优先搜索的方法来计算。首先需要根据数组 edges 来建图，接着使用 dfs() 来求出每个连通块的大小。dfs() 的作用为遍历与它在同一个连通分量重并且未访问过的点，并返回访问的点数。
遍历所有点，如果当前点还没有访问过，则说明遇到了一个新的连通分量，通过 dfs() 来计算当前连通分量的点数 $count$，这个连通分量中的所有点与这个连通分量中的所有点都无法相互到达，因此这个连通分量中的点对答案的贡献是 $count\times (n-count)$。与方法一类似，每个点对会被计算两次，因此最后结果需要除以 2。

实现代码

class Solution {
public:
    long long countPairs(int n, vector<vector<int>> &edges) {
        vector<vector<int>> g(n);
        for (auto &e: edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x); // 建图
        }

        vector<int> vis(n);
        function<int(int)> dfs = [&](int x) -> int {
            vis[x] = true; // 避免重复访问同一个点
            int size = 1;
            for (int y: g[x]) {
                if (!vis[y]) {
                    size += dfs(y);
                }
            }
            return size;
        };

        long long res = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) { // 未访问的点：说明找到了一个新的连通块
                int size = dfs(i);
                res += (long long) size * (n - size);
            }
        }
        return res / 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

复杂度分析

时间复杂度：$O(m+n)$，其中 $m$ 是边数。构造临接表消耗 $O(m+n)$，dfs() 消耗 $O(m+n)$。

空间复杂度：$O(m+n)$。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。