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

难度: Medium

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

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

示例 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 <= 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
不会有重复边。

Submission

运行时间: 220 ms

内存: 62.9 MB

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:

        parent =list(range(n))

        rank = [1]*n 

        # g =[[ ] for _ in range(n)]

        # for a,b in edges:
        #     g[a].append(b)
        #     g[b].append(a)

        def find(x):
            if x == parent[x]:
                return x

            parent[x] = find(parent[x])
            return parent[x]
        def union(x,y):
            rootX = find(x)
            rootY = find(y)

            if rootX!=rootY:
                parent[rootX] =parent[rootY]
                rank[rootY] += rank[rootX]

        for a,b in edges:
            union(a,b)
        

        ans = 0
        # print(rank)
        # print(parent)
        group = []
        size  = 1
        total  = 0
        for i, p in enumerate(parent): #O(n^2)
            if i ==p :
                # ans  += size * rank[p] 
                # total += rank[p]
                # size =total 
                group.append(p)
                

        total = sum(rank[g] for g in group)
        for g in group:
            ans += rank[g]*(total - rank[g])
        return ans//2

Explain

题解使用并查集（Union-Find）来处理图中的连通性问题。首先，每个节点初始化为自己的父节点，通过并查集的union和find操作，将每个边连接的两个节点合并到同一个集合。find操作实现了路径压缩，使得重复查找效率更高。union操作中，将一个集合的根节点指向另一个，同时更新根节点的rank（集合大小）。最后，计算所有不连通的节点对。具体地，首先找出所有的根节点，每个根节点代表一个连通分量。计算每个连通分量的节点数，然后对于每个连通分量，用其节点数乘以剩余所有节点的总数（减去当前连通分量的节点数），得到与当前连通分量中的每个节点不连通的节点对数。最后，为避免重复计算，将结果除以2。

时间复杂度: O(m + n)

空间复杂度: O(n)

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))  # 初始化每个节点的父节点为自身
        rank = [1] * n  # 初始化每个节点的连通分量大小为1

        def find(x):
            if x == parent[x]:
                return x
            parent[x] = find(parent[x])  # 路径压缩
            return parent[x]

        def union(x, y):
            rootX = find(x)
            rootY = find(y)
            if rootX != rootY:
                parent[rootX] = parent[rootY]  # 将一个根节点指向另一个
                rank[rootY] += rank[rootX]  # 更新连通分量的大小

        for a, b in edges:
            union(a, b)  # 对每个边执行union操作

        ans = 0
        group = []
        total = 0
        for i, p in enumerate(parent):  # 查找所有根节点
            if i == p:
                group.append(p)

        total = sum(rank[g] for g in group)  # 计算所有连通分量的总节点数
        for g in group:
            ans += rank[g] * (total - rank[g])  # 计算不连通的节点对数
        return ans // 2  # 除以2避免重复计算

Explore

在并查集的实现中，`rank`数组可以有不同的用途。通常情况下，它被用来表示树的高度以优化树结构，使得树更加平衡，从而提高查找效率。然而，在这个题解中，`rank`数组被用来记录每个连通分量中的节点数量。这样的设计是为了直接利用`rank`数组来计算不连通的节点对数，使得算法实现更为简洁高效。通过这种方式，我们可以直接通过`rank`的值来获取每个连通分量的大小，而无需额外的数据结构或计算。

题解中的`union`操作实际上没有明确考虑树的平衡性，因为它总是将`rootX`的父节点设置为`rootY`。这种方法简化了实现，但可能导致不平衡的树结构，这在极端情况下可能会降低效率。在标准的并查集实现中，会根据`rank`或`size`对两个树的高度或大小进行比较，通常将较小的树连接到较大的树上，从而保持树的平衡，提高操作的效率。因此，如果要优化此题解的性能，应考虑在`union`操作中引入基于`rank`或`size`的比较逻辑。

题解中最后的结果需要除以2是因为在计算不连通的节点对数时，每对节点被计算了两次。例如，如果节点A和节点B不连通，那么在计算过程中会分别计算A到B和B到A作为不连通的节点对。这实际上是同一对节点，因此为了得到正确的节点对数，需要将总数除以2，以去除重复计数的影响。

路径压缩是并查集优化技术中的一个重要方法，其作用是在执行查找操作时缩短树的高度。具体来说，当我们执行`find`操作找到某个节点的根节点时，路径压缩会将查找路径上的所有节点直接连接到根节点上。这样，下次再查找这些节点时，路径将大幅缩短，从而加快查找速度。路径压缩能显著提高并查集的效率，使得几乎所有操作的平均时间复杂度接近常数级别，特别是在大规模数据处理中效果显著。