动态社交网络中的朋友圈合并与关系维护

题目

动态社交网络中的朋友圈合并与关系维护

信息

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

考点

并查集路径压缩,按秩合并优化,动态连通性处理,多操作场景设计

快速回答

该问题要求设计一个支持动态关系维护的并查集结构，核心要点包括：

• 使用路径压缩和按秩合并优化并查集操作
• 实现三种关键操作：添加关系、查询连通性、合并朋友圈
• 处理合并操作时的多根节点协调问题
• 维护动态秩信息确保合并效率
• 注意操作间的时序依赖和状态一致性

问题背景与要求

在社交网络场景中，需要高效处理三种操作：(1) 添加朋友关系 (2) 查询两人是否同属朋友圈 (3) 合并两个朋友圈。随着关系动态变化，需保证所有操作接近常数时间复杂度。

核心原理

1. 并查集优化原理

• 路径压缩：查找时扁平化树结构，使后续查询更快
• 按秩合并：总是将小树合并到大树，控制树高度

2. 多操作协调

• 添加关系：本质是合并两个独立集合
• 合并朋友圈：需先定位两个集合的根节点再合并
• 查询操作：依赖路径压缩保持高效

代码实现

class DynamicUnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.circle_size = [1] * n  # 记录朋友圈大小

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

    def addFriend(self, a, b):
        # 添加朋友关系 = 合并集合
        rootA = self.find(a)
        rootB = self.find(b)
        if rootA == rootB:
            return  # 已在同一集合

        # 按秩合并
        if self.rank[rootA] < self.rank[rootB]:
            self.parent[rootA] = rootB
            self.circle_size[rootB] += self.circle_size[rootA]
        elif self.rank[rootA] > self.rank[rootB]:
            self.parent[rootB] = rootA
            self.circle_size[rootA] += self.circle_size[rootB]
        else:
            self.parent[rootB] = rootA
            self.rank[rootA] += 1
            self.circle_size[rootA] += self.circle_size[rootB]

    def query(self, a, b):
        return self.find(a) == self.find(b)

    def mergeCircles(self, rep1, rep2):
        # 通过代表找到实际根节点
        root1 = self.find(rep1)
        root2 = self.find(rep2)
        if root1 == root2:
            return  # 已在同一朋友圈

        # 按秩合并两个朋友圈
        if self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
            self.circle_size[root2] += self.circle_size[root1]
        elif self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
            self.circle_size[root1] += self.circle_size[root2]
        else:
            self.parent[root2] = root1
            self.rank[root1] += 1
            self.circle_size[root1] += self.circle_size[root2]

最佳实践

• 双优化必须同时使用：单独使用路径压缩或按秩合并无法达到O(α(n))时间复杂度
• 秩的维护策略：仅在秩相等时增加秩，避免过度增长
• 状态一致性：合并时同步更新附加信息（如朋友圈大小）
• 延迟更新：朋友圈大小等元数据可在查询时动态计算（牺牲时间换空间）

常见错误

• 错误1：合并时未使用根节点 → 创建无效环状结构
• 错误2：忘记路径压缩 → 退化为O(n)查询
• 错误3：按秩合并时错误比较秩值 → 树高度失控
• 错误4：未检查是否同集合直接合并 → 破坏数据结构
• 错误5：合并朋友圈时使用非代表节点 → 错误合并子集

复杂度分析

扩展知识

• 动态连通性应用：Kruskal算法、图像连通区域检测、变量等价性推理
• 高级变种：支持删除操作的并查集（使用中间映射层）、带权并查集（维护相对关系）
• 并行优化：多线程环境下使用锁分段或乐观锁控制并发访问
• 现实场景适配：超大规模数据时使用磁盘持久化树结构