并查集的模块实现文件

// unionfind.cpp - 模块实现文件
module UnionFind;

UnionFind::UnionFind(int size) : parent(size), rank(size, 0) {
    std::iota(parent.begin(), parent.end(), 0);
}

int UnionFind::find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];
}

void UnionFind::unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX == rootY) return;  // 已经在同一集合
    
    // 按秩合并：将秩小的树合并到秩大的树下
    if (rank[rootX] >= rank[rootY]) {
        parent[rootY] = rootX;          // rootY 指向 rootX
        if (rank[rootX] == rank[rootY]) // 如果秩相同，增加 rootX 的秩
            rank[rootX]++;
    } 
    else {
        parent[rootX] = rootY;          // 否则 rootX 指向 rootY
    }
}

bool UnionFind::connected(int x, int y) {
    return find(x) == find(y);
}