并查集是解决朋友圈连通性问题的高效工具，通过find（带路径压缩）和union（按秩合并）操作维护不相交集合，初始化每人一集，每合并一次count减1，最终count即朋友圈总数。

并查集（Union-Find）是解决朋友圈这类“社交连通图”问题的高效工具，核心在于快速判断两人是否属于同一圈子（连通），以及合并两个圈子（union）。它不关心具体关系路径，只关注“是否连通”和“如何归并”，时间复杂度接近常数（使用路径压缩 + 按秩合并）。

用并查集建模朋友圈关系

把每个人看作一个节点（通常用 0 到 n−1 的整数编号），每条朋友关系（如 [a, b]）表示 a 和 b 在同一朋友圈。并查集通过维护若干互不相交的集合，来刻画“谁和谁同属一个圈子”。初始化时每人自成一个集合；遇到朋友关系，就 union(a, b)；最后统计剩余的独立集合数量，就是朋友圈总数。

关键操作：find 和 union 的实现要点

标准实现需支持两个核心操作：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

• find(x)：返回 x 所在集合的代表元（根节点），务必配合路径压缩——递归查找时，把沿途所有节点直接挂到根下，下次查询更快；
• union(x, y)：合并 x 和 y 所在集合，推荐用按秩合并（rank 数组记录树高），总是把矮树挂到高树下，避免退化成链表；
• 初始化时，parent[i] = i，rank[i] = 0，count = n（初始 n 个独立圈子）；每次成功 union 后 count 减 1。

处理输入关系并统计朋友圈数量

假设输入是二维数组 relations，如 [[0,1],[1,2],[3,4]]，表示 0–1、1–2、3–4 是朋友：

• 遍历每对关系 [a,b]，调用 union(a, b)；
• 遍历结束后，count 就是剩余朋友圈数；
• 若需输出每个圈子成员，可遍历所有节点，用 find(i) 分组，再按根节点聚合；
• 注意：关系可能重复或自环（如 [2,2]），union 前可用 find 判断是否已连通，避免无效操作。

Java 实现示例（简洁可运行）

以下是一个带路径压缩与按秩合并的完整模板：

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int count;

    public UnionFind(int n) {
        this.count = n;
        this.parent = new int[n];
        this.rank = new int[n];
        for (int i = 0; i  rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
    }

    public int getCount() { return count; }
}

主逻辑只需 new UnionFind(n)，循环调用 union，最后 getCount() 即得答案。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南