并查集用森林模拟动态连通关系，以数组parent[]维护父节点，通过路径压缩和按秩/大小合并实现高效查找与合并，均摊时间接近O(1)。

并查集（Union-Find）本质是用森林模拟动态连通关系：每个连通分量是一棵树，根节点代表整个集合。它不关心路径细节，只快速回答“是否连通”和“如何合并”，因此实现简洁但需兼顾效率。

用数组维护父节点关系
最常用方式是用一个整型数组 parent[]，索引表示元素编号（如 0 到 n−1），值表示其直接父节点：

• 初始时 parent[i] = i，每个元素自成一棵单节点树；
• 根节点满足 parent[x] == x；
• 查找时不断向上跳转，直到抵达根节点。

查找操作要带路径压缩
单纯递归或迭代找根容易退化成链表（最坏 O(n)）。路径压缩在 find(x) 返回根的同时，把路径上所有节点的 parent 直接设为根：

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 递归压缩
    }
    return parent[x];
}

这样后续查找几乎都是 O(1)，均摊时间接近常数。

Alibabacloud Sdk Client Initialization For Java

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

下载

合并操作要按秩或按大小合并
union(x, y) 先找二者根节点，若不同，则把小树挂到大树下，防止树过高：

• 按秩（rank）：记录每棵树的近似高度，总是把低秩树根连到高秩树根；
• 按大小（size）：记录每棵树的节点数，把节点少的树根连到节点多的树根。
  例如按大小：

  if (size[rootX] < size[rootY]) {
    parent[rootX] = rootY;
    size[rootY] += size[rootX];
  } else {
    parent[rootY] = rootX;
    size[rootX] += size[rootY];
  }

连通分量数量可实时维护
初始化时 count = n；每次成功 union 就 count--；connected(x, y) 只需 find(x) == find(y)；count() 直接返回变量值。无需遍历，响应极快。

不复杂但容易忽略优化细节。