Medium

题目描述

给你一个整数 n。现有一个包含 n 个节点的无向图，节点编号从 0 到 n - 1。给你一个二维整数数组 edges，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间存在一条无向边。

返回图中无法互相到达的不同节点对的数目。

示例 1：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：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]]

提示：

  • 1 <= n <= 10^5
  • 0 <= edges.length <= 2 * 10^5
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • 没有重复的边

解题思路

这道题的核心思路是找到图中的所有连通分量，然后统计不同连通分量之间的节点对数。

解题步骤：

  1. 找连通分量：使用并查集、DFS 或 BFS 找到图中所有的连通分量及其大小
  2. 计算无法到达的节点对：对于任意两个不同连通分量，它们之间的所有节点对都无法互相到达

三种主要方法：

  1. 并查集（推荐）：时间复杂度接近 O(n)，代码简洁
  2. DFS：遍历每个未访问的节点，统计连通分量大小
  3. BFS：类似 DFS，但使用队列实现

计算公式：

如果有连通分量大小分别为 size1, size2, ..., sizek，那么无法到达的节点对数为：

  • 总的节点对数：n * (n-1) / 2
  • 连通分量内部可达的节点对数：∑(sizei * (sizei-1) / 2)
  • 答案 = 总数 - 内部可达数

或者直接计算：对于每个连通分量，它与其他所有连通分量的节点都无法到达，即 ∑(sizei * (n - sizei)) / 2。

这里采用并查集解法，因为它在处理连通性问题时最为高效。

代码实现

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        auto unite = [&](int x, int y) {
            parent[find(x)] = find(y);
        };
        
        for (auto& edge : edges) {
            unite(edge[0], edge[1]);
        }
        
        unordered_map<int, int> componentSize;
        for (int i = 0; i < n; i++) {
            componentSize[find(i)]++;
        }
        
        long long result = 0;
        long long remaining = n;
        for (auto& [root, size] : componentSize) {
            remaining -= size;
            result += (long long)size * remaining;
        }
        
        return result;
    }
};

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            parent[find(x)] = find(y)
        
        for a, b in edges:
            unite(a, b)
        
        component_size = {}
        for i in range(n):
            root = find(i)
            component_size[root] = component_size.get(root, 0) + 1
        
        result = 0
        remaining = n
        for size in component_size.values():
            remaining -= size
            result += size * remaining
        
        return result

public class Solution {
    public long CountPairs(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        void Unite(int x, int y) {
            parent[Find(x)] = Find(y);
        }
        
        foreach (var edge in edges) {
            Unite(edge[0], edge[1]);
        }
        
        var componentSize = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            int root = Find(i);
            componentSize[root] = componentSize.GetValueOrDefault(root, 0) + 1;
        }
        
        long result = 0;
        long remaining = n;
        foreach (var size in componentSize.Values) {
            remaining -= size;
            result += (long)size * remaining;
        }
        
        return result;
    }
}

var countPairs = function(n, edges) {
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function unite(x, y) {
        parent[find(x)] = find(y);
    }
    
    for (const [a, b] of edges) {
        unite(a, b);
    }
    
    const componentSize = new Map();
    for (let i = 0; i < n; i++) {
        const root = find(i);
        componentSize.set(root, (componentSize.get(root) || 0) + 1);
    }
    
    let result = 0;
    let remaining = n;
    for (const size of componentSize.values()) {
        remaining -= size;
        result += size * remaining;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
并查集O(n + m·α(n))O(n)
DFS/BFSO(n + m)O(n + m)

其中 n 是节点数，m 是边数，α(n) 是阿克曼函数的反函数，在实际应用中可视为常数。

相关题目