朋友圈数量统计

题目

朋友圈数量统计

信息

• 类型：问答
• 难度：⭐

考点

并查集实现,连通分量统计,路径压缩

快速回答

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

• 初始化并查集：每个用户作为独立集合，父节点指向自己
• 遍历关系列表：对每对关系执行合并操作（union）
• 合并时检查根节点：若不同则合并，同时减少朋友圈计数
• 使用路径压缩优化查找效率
• 最终朋友圈数量等于剩余独立集合数量

问题描述

给定一个社交网络中用户间的朋友关系列表（例如：[[1,2], [2,3]] 表示用户1和2是朋友，用户2和3是朋友），要求计算整个网络中的朋友圈数量。朋友关系具有传递性：若A-B是朋友且B-C是朋友，则A-C也是朋友（属于同一个朋友圈）。

原理说明

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

• 查找（Find）：确定元素所在集合的根节点
• 合并（Union）：将两个集合合并为一个
• 路径压缩：优化查找操作，使树结构更扁平
• 连通分量统计：维护独立集合的数量

代码示例（Python）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(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:
            self.parent[rootY] = rootX
            self.count -= 1  # 合并后集合数量减少

def count_circles(relationships, n):
    uf = UnionFind(n)
    for a, b in relationships:
        uf.union(a, b)  # 处理每对关系
    return uf.count

# 测试用例
relationships = [[0,1], [1,2], [3,4]]  # 用户0-1-2相连，3-4相连
n = 5  # 总用户数
print(count_circles(relationships, n))  # 输出：2（两个朋友圈）

最佳实践

• 路径压缩：在find操作中扁平化树结构，将时间复杂度降至近O(1)
• 及时更新计数：仅在成功合并时减少集合计数
• 索引处理：用户ID若从1开始，需映射到0-based索引

常见错误

• 未初始化父节点：忘记将每个元素的父节点初始化为自身
• 遗漏路径压缩：导致树退化成链表，查找效率降为O(n)
• 重复合并：未检查根节点是否相同就减少计数，导致计数错误
• 索引越界：用户ID超出总人数范围

扩展知识

• 按秩合并：记录树高度，总是将矮树合并到高树上（可进一步优化）
• 动态处理：支持实时添加新关系并更新朋友圈数量
• 获取集合成员：扩展数据结构记录每个集合的所有元素
• 复杂度分析：m次操作总时间复杂度O(mα(n))，其中α是反阿克曼函数