社交网络中的朋友圈数量

题目

社交网络中的朋友圈数量

信息

• 类型：问答
• 难度：⭐⭐

考点

并查集实现,路径压缩优化,按秩合并优化,连通分量统计

快速回答

使用并查集解决朋友圈问题的要点：

• 初始化并查集，每个用户作为独立集合
• 遍历关系矩阵，合并直接朋友所在的集合
• 使用路径压缩和按秩合并优化性能
• 统计根节点数量（即 parent[i] == i 的节点）作为朋友圈数量
• 时间复杂度：O(n² α(n))，空间复杂度：O(n)

问题描述

给定 n 个用户的社交关系矩阵 M（n x n），其中 M[i][j]=1 表示用户 i 和 j 是直接朋友（关系对称）。朋友的朋友属于同一朋友圈，计算总的朋友圈数量。

原理说明

并查集（Union-Find）是解决动态连通性问题的经典数据结构，核心操作：

• Find：查找元素的根节点（代表元）
• Union：合并两个元素所在的集合
• 路径压缩：Find 过程中扁平化树结构，加速后续查询
• 按秩合并：Union 时总是将小树附加到大树上，避免退化

代码实现（Python）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 初始独立集合数

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return

        # 按秩合并
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        self.count -= 1

def findCircleNum(M):
    n = len(M)
    uf = UnionFind(n)

    for i in range(n):
        for j in range(i+1, n):  # 利用对称性，只需遍历一半
            if M[i][j] == 1:
                uf.union(i, j)

    return uf.count

最佳实践

• 双优化策略：同时使用路径压缩和按秩合并，使操作均摊时间复杂度接近 O(α(n))
• 对称遍历：关系矩阵对称，只需遍历上三角避免重复操作
• 实时计数：在 Union 操作中维护连通分量计数，避免最终全扫描

常见错误

• 未优化导致超时：未使用路径压缩/按秩合并时，最坏时间复杂度 O(n²)
• 错误统计：直接统计 parent 数组中的不同值（需用 find 后结果）
• 重复合并：未跳过 M[i][i] 或重复处理对称关系
• 空间浪费：使用 O(n²) 空间存储中间结果（实际只需 O(n)）

扩展知识

• 动态连通性：并查集擅长处理动态添加的连接关系
• 阿克曼函数：α(n) 是其反函数，增长极慢（n=10^600 时 α(n)<5）
• 变种问题：带权并查集（如食物链问题）、离线查询（Tarjan's LCA）
• 替代方案：DFS/BFS 也可求解，但无法高效处理动态增边场景