高效处理动态连通性问题
并查集是一种维护多个不相交集合的数据结构，支持两个核心操作：
时间复杂度：接近 $$ O(1) $$（路径压缩 + 按秩合并）
路径压缩：在 Find 时将节点直接指向根节点，扁平化树结构
按秩合并：将深度小的树合并到深度大的树下，保持树平衡
class DSU {
private:
vector parent, rank;
public:
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++)
parent[i] = i;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
// 按秩合并
if (rank[x] < rank[y])
swap(x, y);
parent[y] = x;
if (rank[x] == rank[y])
rank[x]++;
}
bool same(int x, int y) {
return find(x) == find(y);
}
};