LeetCode 2316. 统计无向图中无法互相到达点对数：：广度优先搜索（BFS）

【LetMeFly】2316.统计无向图中无法互相到达点对数：广度优先搜索（BFS）

力扣题目链接：https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。

 

示例 1：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。

示例 2：

输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

 

提示：

• 1 <= n <= 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• 不会有重复边。

方法一：广度优先搜索BFS

这道题的关键就是统计出每个子图的大小。假设原图是由大小为a、b、c的三个子图构成的，那么答案$ans=a\times (b+c)+b\times (a+c)+c\times (a+b)=a\times (n-a)+b\times (n-b)+c\times (n-c)$。

怎么统计出每个子图有多少个节点呢？广搜一遍就行了。使用visited数组来记录哪个节点被遍历过，从$0$到$n-1$枚举，遇到没遍历过的节点就开始广搜，统计这个子图的节点个数并标记处理过的节点。

• 时间复杂度$O(n+len(edges))$
• 空间复杂度$O(n+len(edges))$

AC代码

C++

typedef long long ll;
class Solution {
public:
    ll countPairs(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto& v : edges) {
            graph[v[0]].push_back(v[1]);
            graph[v[1]].push_back(v[0]);
        }
        vector<ll> sizes;
        vector<bool> visited(n);
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }
            int cntNode = 0;
            visited[i] = true;
            queue<int> q;
            q.push(i);
            while (q.size()) {
                int thisNode = q.front();
                cntNode++;
                q.pop();
                for (int t : graph[thisNode]) {
                    if (!visited[t]) {
                        visited[t] = true;
                        q.push(t);
                    }
                }
            }
            sizes.push_back(cntNode);
        }
        ll ans = 0;
        for (ll t : sizes) {
            ans += t * (n - t);
        }
        return ans / 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

Python

# from typing import List

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        visited = [False] * n
        sizes = []
        for i in range(n):
            if visited[i]:
                continue
            cntNode = 0
            visited[i] = True
            q = [i]
            while q:
                thisNode = q.pop()
                cntNode += 1
                for t in graph[thisNode]:
                    if not visited[t]:
                        visited[t] = True
                        q.append(t)
            sizes.append(cntNode)
        ans = 0
        for t in sizes:
            ans += t * (n - t)
        return ans // 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

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133962709