《并查集的黑科技：路径压缩×按秩合并×带权扩展｜算法核心原理与工程级实践指南》

A(m, n) = 
    n+1                  if m=0
    A(m-1, 1)           if m>0 and n=0
    A(m-1, A(m, n-1))   otherwise

class UnionFind {
private:
    vector<int> fa;    // 父节点数组
    vector<int> cnt;   // 连通块内点的数量
    vector<int> rank;  // 秩（树的高度）
    int count = 0;     // 新增：连通块数量
    
public:
    // 1. 初始化
    UnionFind(int n) {   
        fa.resize(n + 1);
        rank.resize(n + 1, 1);
        cnt.resize(n + 1, 1);
        count = n;      // 初始每个节点都是独立连通块，总共有n个
        for(int i = 1; i <= n; ++i) fa[i] = i;
    }

    // 2. 查找根节点（路径压缩）
    int find(int x) {    
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    // 3. 合并集合（按秩合并）
    void unite(int a, int b) { 
        int x = find(a), y = find(b);
        if (x == y) return;

        // 合并时连通块数量减少1
        count--;

        // 按秩合并
        if (rank[x] < rank[y]) {
            fa[x] = y;
            cnt[y] += cnt[x];
        } else {
            fa[y] = x;
            cnt[x] += cnt[y];
            if (rank[x] == rank[y]) rank[x]++;
        }
    }

    // 4. 判断连通性
    bool isConnected(int x, int y) { 
        return find(x) == find(y);
    }

    // 5. 获取连通块大小
    int getCnt(int x) {
        return cnt[find(x)];
    }

    // 6. 获取连通块数量
    int getCount() const {
        return count;
    }
};

class WeightedUnionFind {
private:
    vector<int> parent;  // 父节点数组
    vector<int> rank;    // 秩（树的高度）
    vector<double> weight; // 权重数组：记录节点到父节点的关系权重

public:
    WeightedUnionFind(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0); // 初始父节点为自身
        rank.resize(n, 1);
        weight.resize(n, 1.0); // 初始权重为1.0
    }

    // 查找操作（带路径压缩）
    pair<int, double> find(int x) {
        if (parent[x] != x) {
            auto [root, w] = find(parent[x]); // 递归查找根节点
            parent[x] = root;                 // 路径压缩
            weight[x] *= w;                   // 更新当前节点到根的权重
        }
        return {parent[x], weight[x]};
    }

    // 合并操作（带权重关系处理）
    void unite(int x, int y, double value) {
        auto [rootX, wX] = find(x); // x到根的权重wX
        auto [rootY, wY] = find(y); // y到根的权重wY
        
        if (rootX == rootY) return;

        // 合并策略（按秩合并）
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
            weight[rootX] = value * wY / wX; // 计算新权重关系
        } else {
            parent[rootY] = rootX;
            weight[rootY] = wX / (value * wY); // 权重关系反向
            if (rank[rootX] == rank[rootY]) 
                rank[rootX]++;
        }
    }

    // 查询x和y的关系值
    double getValue(int x, int y) {
        auto [rootX, wX] = find(x);
        auto [rootY, wY] = find(y);
        if (rootX != rootY) return -1.0; // 不连通
        return wX / wY; // 返回x/y的值
    }
};

a*rootX = value*(b*rootY)=> rootX = (value*b/a) * rootY

#include <vector>
#include <unordered_map>
#include <set>
#include <numeric>
#include <algorithm>
#include <iostream>

class DisjointSet {
private:
    std::unordered_map<int, int> element_to_idx; // 元素到索引的映射
    std::vector<int> parent;                     // 父节点数组
    std::vector<int> rank;                       // 秩数组（树的高度）

public:
    // 构造函数：离散化元素并初始化并查集
    DisjointSet(const std::vector<int>& elements) {
        // 1. 去重并排序
        std::set<int> unique_sorted_elements(elements.begin(), elements.end());

        // 2. 建立元素到索引的映射
        int idx = 0;
        for (int elem : unique_sorted_elements) {
            element_to_idx[elem] = idx++;
        }

        // 3. 初始化 parent 和 rank
        parent.resize(unique_sorted_elements.size());
        std::iota(parent.begin(), parent.end(), 0); // 初始父节点为自身
        rank.resize(unique_sorted_elements.size(), 1); // 初始秩为1
    }

    // 查找元素的根节点（路径压缩）
    int find(int x) {
        int x_idx = element_to_idx[x];
        if (parent[x_idx] != x_idx) {
            parent[x_idx] = find_by_idx(parent[x_idx]); // 路径压缩
        }
        return parent[x_idx];
    }

private:
    // 辅助函数：通过索引查找根节点（递归实现）
    int find_by_idx(int x_idx) {
        if (parent[x_idx] != x_idx) {
            parent[x_idx] = find_by_idx(parent[x_idx]); // 路径压缩
        }
        return parent[x_idx];
    }

public:
    // 合并两个集合（按秩合并）
    void union_sets(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if (x_root == y_root) return;

        // 按秩合并：小树合并到大树
        if (rank[x_root] < rank[y_root]) {
            parent[x_root] = y_root;
        }
        else {
            parent[y_root] = x_root;
            if (rank[x_root] == rank[y_root]) {
                rank[x_root]++;
            }
        }
    }
};

int main() {
    // 测试用例
    std::vector<int> elements = { 1, 3, 7, 100000, 3, 1 };
    DisjointSet ds(elements);

    ds.union_sets(1, 3);
    ds.union_sets(7, 100000);

    std::cout << std::boolalpha << (ds.find(1) == ds.find(3)) << std::endl;     // 输出 true
    std::cout << (ds.find(7) == ds.find(100000)) << std::endl; // 输出 true
    std::cout << (ds.find(1) == ds.find(7)) << std::endl;     // 输出 false

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
#include <tuple> // 添加元组支持

using namespace std;

class RollbackUnionFind {
private:
    // 操作记录类型：子根 | 父根 | 原父秩
    using Operation = tuple<int, int, int>;

    vector<int> fa;     // 父节点数组
    vector<int> rank;   // 树的高度
    stack<Operation> st; // 操作记录栈
    int count;          // 连通块数量

public:
    // 初始化
    RollbackUnionFind(int n) : count(n) {
        fa.resize(n + 1);
        rank.resize(n + 1, 1);
        for (int i = 1; i <= n; ++i)
            fa[i] = i;
    }

    // 查找根节点（无路径压缩）
    int find(int x) const {
        while (fa[x] != x)
            x = fa[x];
        return x;
    }

    // 合并操作
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            st.emplace(-1, -1, -1); // 无效操作标记
            return false;
        }

        // 按秩合并
        if (rank[x] < rank[y]) {
            st.emplace(x, y, rank[y]);
            fa[x] = y;
        }
        else {
            st.emplace(y, x, rank[x]);
            fa[y] = x;
            if (rank[x] == rank[y])
                ++rank[x]; // 树高增加
        }
        --count; // 连通块数量减少
        return true;
    }

    // 撤销操作
    void rollback() {
        if (st.empty()) return;
        Operation t = st.top();
        int child = get<0>(t), parent_root = get<1>(t), old_rank = get<2>(t);
        st.pop();

        if (child == -1) return; // 无效操作

        // 恢复父子关系
        fa[child] = child;
        // 恢复原秩值
        if (rank[parent_root] != old_rank) {
            rank[parent_root] = old_rank;
        }
        ++count; // 连通块数量恢复
    }

    // 获取当前连通块数量
    int getCount() const { return count; }

    // 判断是否连通
    bool isConnected(int x, int y) const {
        return find(x) == find(y);
    }
};

int main() {
    RollbackUnionFind uf(5); // 5个元素

    uf.unite(1, 2);    // 连通块：{1,2}, {3}, {4}, {5} (count=4)
    uf.unite(3, 4);    // 连通块：{1,2}, {3,4}, {5} (count=3)
    uf.rollback();      // 撤销上一步 (count=4)
    uf.unite(2, 3);     // 连通块：{1,2,3}, {4}, {5} (count=3)

    cout << uf.isConnected(1, 3) << endl; // 输出1（连通）
    uf.rollback();      // 撤销unite(2,3)
    cout << uf.isConnected(1, 3) << endl; // 输出0（不连通）
    cout << uf.getCount() << endl;        // 输出4
}

class DynamicUnionFind {
private:
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;
public:
    void add(int x) {
        if (!parent.count(x)) {
            parent[x] = x;
            rank[x] = 1;
        }
    }
    // find 和 unite 方法与标准实现类似
};

class UnionFind {
public:
    unordered_map<int, int> fa;
    int count = 0; // 总共有多少不连通的并查集

    int find(int x) {    
        // 构建并查集时候，假如key值不在并查集中则构建哈希表映射，count++
        if(fa.find(x) == fa.end()){
            fa[x] = x;
            count++;
        }
        // 查找并查集的头节点并优化
        if(fa[x] != x) fa[x] = find(fa[x]);
        return fa[x];
    }

    // 合并集合
    void unite(int a, int b) { 
        int x = find(a), y = find(b);
        if (x == y) return;
        fa[x] = y;
        count--; 
    }
};

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

Yes
No
Yes

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int p[N];

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    char op;
    int a, b;
    while(m--){
        cin >> op >> a >> b;
        if(op == 'M'){
            p[find(a)] = find(b); // 集合合并操作
        }
        else{
            if(find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

Yes
2
3

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;

int fa[N], cnt[N];
int n, m;

// 1. 初始化
void init()
{
    for(int i = 1; i <= n; i++){
        fa[i] = i;
        cnt[i] = 1;
    }
}

// 2. 查询根节点
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// 3. 合并连通块
void merge(int a, int b)
{
    int x = find(a), y = find(b);
    fa[x] = y;
    cnt[y] += cnt[x]; // y 连通块 + x 连通块内点数量
}

// 4. 判断连通
bool isconnected(int a, int b){
    return find(a) == find(b);
}

int main()
{
    cin >> n >> m;
    init();
    string op;
    int a, b;
    while(m--)
    {
        cin >> op;
        if(op == "C") {
            cin >> a >> b;
            // 更新连通块数量之前一定需要先判断两者是否在一起
            if(!isconnected(a, b))merge(a, b);
        }
        else if(op == "Q1"){
            cin >> a >> b;
            if(isconnected(a, b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else{
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
}

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

3

#include <iostream>
using namespace std;
int fa[200000];
int n, k;
void init(){
    for(int i = 1;i <= 3*n; ++i) fa[i]=i;
}
int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int a, int b){
    int x = find(a), y = find(b);
    fa[x] = y; 
}

int main()
{
    cin >> n >> k;
    init();
    int ans = 0;
    while(k--)
    {
        int D, x, y;
        cin >> D >> x >> y;
        if(x > n || y > n) ans++;
        else if(D == 1)
        {
            // 如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误.
            if(find(x) == find(y + n) || find(x) == find(y + n + n)) ans++;
            else{
                merge(x, y); // 同类域
                merge(x + n, y + n); // 捕食域
                merge(x + n + n, y + n + n); // 天敌域
            }
        }
        else // x 吃 y
        {
            // x就是y,或者他们是同类,再或者是y的同类中有x
            if(x == y || find(x) == find(y) || find(x) == find(y+n)) ans++; // 都是假话
            else{
                merge(x, y + n + n);     // x 同类域 加入 y 天敌域
                merge(x + n, y);         // x 捕食域 加入 y 同类域
                merge(x + n + n, y + n); // x 天敌域 加入 y 捕食域
            }
        }
    }

    cout << ans << endl;
    return 0;
}

#include <iostream>
using namespace std;

const int N = 500010;
int p[N], d[N]; //size[]表示的是每一个集合点的数量
int n, k;

int find(int x)
{
    if (p[x] != x){
        int t = find(p[x]);  //开始递归；最终用t储存根节点
        d[x] += d[p[x]];     //在递归过程中求得每个点到根节点的距离
        p[x] = t;            //将每个点的父节点指向根节点
    }
    return p[x];           //返回父节点
}

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++) p[i] = i;

	int res = 0;
	while (k--)
	{
		int D, x, y;
		cin >> D >> x >> y;
		int px = find(x), py = find(y); // px,py分别储存根节点
		if (x > n || y > n) res++;
		else if(D == 1){
		    if (px == py && (d[x] - d[y]) % 3) res++; //d[x]-d[y]!=0说明两个不是同类
			else if (px != py){
				p[px] = py;
				d[px] = d[y] - d[x]; //(d[x]+d[px]-d[y])%3==0
			}
		}
		else{
	        if (px == py && (d[x] - d[y] - 1) % 3) res++;   // x,y祖宗相同，并且x y 属于同类
			else if (px != py){
				p[px] = py;
				d[px] = d[y] + 1 - d[x]; //(d[x]+d[px]-d[y]-1)%3==0
			}
		}
	}
	cout << res << endl;
	return 0;
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    UnionFind uf(n);
    for (int i = 0; i < n; i++) //由于该矩阵对称，只考虑右上角
    {
        for (int j = i + 1; j < n; j++)
        {
            if (isConnected[i][j] == 1) uf.unite(i, j);
        }
    }
    // 下面两种获取连通块数量的方法都行
    int ans = 0;
    for (int i = 0; i < n; i++){
        if (uf.find(i) == i) ans++;
    }
    // return ans;
    return uf.getCount();
}

int makeConnected(int n, vector<vector<int>>& connections) {
    if(connections.size() < n - 1) return -1;
    UnionFind uf(n);
    int extra = 0;
    for(auto& conn: connections){
        uf.unite(conn[0], conn[1]);
    }

    return uf.getCount() - 1;
}

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    UnionFind uf(n+1); // 节点编号从1开始
    
    for(auto& e : edges) {
        if(uf.isConnected(e[0], e[1]))
            return {e[0], e[1]};
        uf.unite(e[0], e[1]);
    }
    return {};
}

int numIslands(vector<vector<char>>& grid) {
    if(grid.empty()) return 0;
    int n = grid.size(), m = grid[0].size();
    UnionFind uf(n * m);
    int water = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == '0') {
                water++; // 统计水域
                continue;
            }
            int ind = i * m + j + 1; // 当前单元格的索引
            // 1. 合并右边相邻的陆地
            if (j + 1 < m && grid[i][j + 1] == '1') uf.unite(ind, ind + 1);   
            // 2. 合并下边相邻的陆地
            if (i + 1 < n && grid[i + 1][j] == '1') uf.unite(ind, ind + m);
        }
    }
    // 求岛屿数量的方法一
    int ans = 0; //计算连通岛屿中根节点的数目
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            int ind = i * m + j + 1;
            if (grid[i][j] == '1' && uf.find(ind) == ind) ans++;
        }
    }

    // 求岛屿数量的方法二
    // uf.getCount() 返回的是 所有节点的连通块总数 （包括陆地和水域）
    // 因此需要从总连通块数中 减去水域的数量 
    return uf.getCount() - water;
}

bool equationsPossible(vector<string>& equations) {
    UnionFind uf(26);
    // 1. 把所有等式放入连通集里
    for(auto &eq: equations){
        int x = eq[0] - 'a', y = eq[3] - 'a';
        if(eq[1] == '='){
            uf.unite(x, y);
        }
    }
    // 2. 判断不等式
    for(auto &eq: equations){
        int x = eq[0] - 'a', y = eq[3] - 'a';
        if(eq[1] == '!'){
            if(uf.isConnected(x, y)) return false;
        }
    }
    return true;
}

// 方法二: 带权并查集来写, 设置默认权重为 1
bool equationsPossible(vector<string>& equations) {
    WeightedUnionFind uf(26); // 26个小写字母
    
    // 处理所有等式
    for (auto& eq : equations) {
        if (eq[1] == '=') {
            int x = eq[0]-'a', y = eq[3]-'a';
            uf.unite(x, y, 1.0); // x/y=1.0
        }
    }
    
    // 验证不等式
    for (auto& eq : equations) {
        if (eq[1] == '!') {
            int x = eq[0]-'a', y = eq[3]-'a';
            if (uf.getValue(x, y) == 1) // 检查是否相等
                return false;
        }
    }
    return true;
}

vector<double> calcEquation(vector<vector<string>>& equations, 
                           vector<double>& values,
                           vector<vector<string>>& queries) {
    unordered_map<string, int> str2id;
    int id = 0;
    
    // 字符串映射为数字ID
    for (auto& eq : equations) {
        if (!str2id.count(eq[0])) str2id[eq[0]] = id++;
        if (!str2id.count(eq[1])) str2id[eq[1]] = id++;
    }
    
    WeightedUnionFind uf(id);
    // 建立关系
    for (int i = 0; i < equations.size(); ++i) {
        int x = str2id[equations[i][0]];
        int y = str2id[equations[i][1]];
        uf.unite(x, y, values[i]); // x = values[i] * y
    }
    
    // 处理查询
    vector<double> res;
    for (auto& q : queries) {
        if (!str2id.count(q[0]) || !str2id.count(q[1])) {
            res.push_back(-1.0);
            continue;
        }
        int x = str2id[q[0]], y = str2id[q[1]];
        res.push_back(uf.getValue(x, y));
    }
    return res;
}

class DirectedUnionFind {
private:
    vector<int> parent; // 父节点（带路径压缩）
    vector<int> edgeTo; // 显式记录每个节点的直接父节点
    
public:
    DirectedUnionFind(int n) {
        parent.resize(n+1);
        edgeTo.resize(n+1, -1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) { // 路径压缩查找根节点
        return x == parent[x] ? x : parent[x] = find(parent[x]);
    }

        int unite(int u, int v) { // u是v的父节点
        if (edgeTo[v] != -1) // 子节点v已经有父节点
            return v; 

        int rootU = find(u);
        if (rootU == find(v)) // 形成环（u和v已连通）
            return v;

        edgeTo[v] = u;       // v的直接父节点是u
        parent[v] = rootU;   // 合并到u的根
        return -1;
    }
};

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        // 记录入度为 2 的节点的两条侯选边
        vector<int> candidate1, candidate2; 
        unordered_map<int, int> inDegree;
        
        // 检测入度为2的节点
        for (auto& e : edges) {
            if (++inDegree[e[1]] == 2) {
                // 逆序遍历找到所有指向该节点的边
                vector<int> candidates; // 临时存储候选边的索引
                for (int i = n-1; i >= 0; --i) {
                    if (edges[i][1] == e[1]) {
                        candidates.push_back(i);
                        if (candidates.size() == 2) break; // 只需要最后两个
                    }
                }
                // 根据索引顺序赋值候选边
                candidate2 = edges[candidates[0]]; // 最后出现的边（索引较大）
                candidate1 = edges[candidates[1]]; // 倒数第二个出现的边
                break;
            }
        }
        
         DirectedUnionFind uf(n);
        // 处理入度=2的情况
        if (!candidate1.empty()) {
            // 先尝试删除最后出现的候选边candidate2
            bool hasConflict = false;
            for (auto& e : edges) {
                if (e == candidate2) continue;
                if (uf.unite(e[0], e[1]) != -1) {
                    hasConflict = true;
                    break;
                }
            }
            if (!hasConflict) return candidate2; // 删除candidate2后合法

            // 再验证candidate1
            uf = DirectedUnionFind(n);
            for (auto& e : edges) {
                if (e == candidate1) continue;
                if (uf.unite(e[0], e[1]) != -1) 
                    return candidate2; // 必须删除candidate2
            }
            return candidate1; // 可安全删除candidate1
        }
        
        // 处理环的情况
        for (auto& e : edges) {
            if (uf.unite(e[0], e[1]) != -1)
                return e;
        }
        return {};
    }
};

class AccountUnionFind {
public:
    vector<int> parent;
    vector<string> owner; // 每个邮箱的账户名
    unordered_map<string, int> email2id; 
    
public:
    AccountUnionFind(const vector<vector<string>>& accounts) {
        int id = 0;
        // 邮箱离散化并建立映射
        for (auto& acc : accounts) {
            for (int i = 1; i < acc.size(); ++i) {
                string email = acc[i];
                if (!email2id.count(email)) {
                    email2id[email] = id++;
                    owner.push_back(acc[0]); // 保存账户名
                }
            }
        }
        parent.resize(id);
        iota(parent.begin(), parent.end(), 0); // 初始化父节点
    }

    int find(int x) {
        return x == parent[x] ? x : parent[x] = find(parent[x]);
    }

    void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY)
            parent[rootY] = rootX;
    }

    vector<vector<string>> getMerged() {
        unordered_map<int, set<string>> groups;
        
        // 根据根节点分组收集邮箱
        for (auto& [email, id] : email2id) {
            int root = find(id);
            groups[root].insert(email);
        }
        
        // 生成结果
        vector<vector<string>> res;
        for (auto& [root, emails] : groups) {
            vector<string> acc{owner[root]};
            acc.insert(acc.end(), emails.begin(), emails.end());
            res.push_back(acc);
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        AccountUnionFind uf(accounts);
        
        // 合并同一账户的邮箱
        for (auto& acc : accounts) {
            if (acc.size() < 2) continue;
            string firstEmail = acc[1];
            int firstId = uf.email2id.at(firstEmail); // 使用成员变量
            for (int i = 2; i < acc.size(); ++i) {
                string email = acc[i];
                int id = uf.email2id.at(email);
                uf.unite(firstId, id);
            }
        }
        
        return uf.getMerged();
    }
};

class Solution {
public:
    vector<int> parent, cnt;

    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            parent[fx] = fy;
            cnt[fy] += cnt[fx]; // 维护连通块大小
        }
    }

    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        unordered_map<int, int> num_map;
        int idx = 0;
        // 离散化去重
        for (int num : nums) {
            if (!num_map.count(num)) {
                num_map[num] = idx++;
                parent.push_back(idx-1);
                cnt.push_back(1);
            }
        }
        // 合并相邻数字
        for (auto& [num, id] : num_map) {
            if (num_map.count(num+1)) 
                merge(id, num_map[num+1]);
            if (num_map.count(num-1)) 
                merge(id, num_map[num-1]);
        }
        return *max_element(cnt.begin(), cnt.end());
    }
};

class UnionFind {
public:
    unordered_map<int, int> fa;
    int count = 0; // 总共有多少不连通的并查集

    int find(int x) {    
        // 构建并查集时候，假如key值不在并查集中则构建哈希表映射，count++
        if(fa.find(x) == fa.end()){
            fa[x] = x;
            count++;
        }
        // 查找并查集的头节点并优化
        if(fa[x] != x) fa[x] = find(fa[x]);
        return fa[x];
    }

    // 合并集合
    void unite(int a, int b) { 
        int x = find(a), y = find(b);
        if (x == y) return;
        fa[x] = y;
        count--; 
    }
};
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        UnionFind uf;
        for(auto &stone: stones){
            uf.unite(stone[0] + 10001, stone[1]);
        }
        return stones.size() - uf.count;
    }
};

class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        int m = *max_element(nums.begin(), nums.end());
        UnionFind uf(m + 1);
        for(int num: nums){
            for(int i = 2; i * i <= num; i++){
                if(num % i == 0){
                    // [num, 公因数]
                    uf.unite(num, i); 
                    uf.unite(num, num / i); 
                }
            }
        }

        // 根节点映射
        vector<int> cnt(m + 1);
        int ans = 0;
        for(int num: nums){
            int root = uf.find(num); 
            cnt[root]++;
            ans = max(ans, cnt[root]);
        }
        return ans;
    }
};

class UnionFind {
private:
    vector<int> fa;    // 父节点数组
    vector<int> rank;  // 秩（树的高度）
    int count = 0;     // 新增：连通块数量
    
public:
    // 1. 初始化
    UnionFind(int n) {   
        fa.resize(n + 1);
        rank.resize(n + 1, 1);
        count = n;      // 初始每个节点都是独立连通块，总共有n个
        for(int i = 1; i <= n; ++i) fa[i] = i;
    }

    // 2. 查找根节点（路径压缩）
    int find(int x) {    
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    // 3. 合并集合（按秩合并）
    bool unite(int a, int b) { 
        int x = find(a), y = find(b);
        if (x == y) return false;

        // 合并时连通块数量减少1
        count--;

        // 按秩合并
        if (rank[x] < rank[y]) {
            fa[x] = y;
        } else {
            fa[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
        return true;
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        //n * n的网格
        //以row = 0...n，col = 0...n 将所有点存入并查集，并将正方形网格轮廓的各个点连接在一起，表示初始时有一个正方形的环
        //再遍历所有的 / & \\ ，根据其位置连接点。连接过程中如果 两个点的根节点相同，说明新形成了一个环
        //(n + 1) (n + 1) 个点
        UnionFind uf((n + 1) * (n + 1));
        int res = 1; // 初始时有一个正方形
        for(int i = 0; i < n; i++){
            uf.unite(i, i + 1); // 最顶行
            uf.unite(n * (n + 1) + i, n * (n + 1) + i + 1); // 最底行
            uf.unite((n + 1) * i, (n + 1) * (i + 1)); // 最左列
            uf.unite((n + 1) * (i + 1) - 1, (n + 1) * (i + 2) - 1); // 最右列
        }
        // 遍历 / 和 '\\'
        char c = ' ';
        int pos = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                c = grid[i][j];
                pos = i * (n + 1) + j; // 找到左上角的下标
                // 连接右上角和左下角
                if(c == '/'){ 
                    if(!uf.unite(pos + 1, pos + n + 1))res++;
                }
                else if(c == '\\'){
                    if(!uf.unite(pos, pos + n + 2))res++;
                }
            }
        }
        return res;
    }
};

// 使用内存池优化动态分配
class MemoryPoolUnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    stack<int> recycled; // 回收的节点索引
public:
    int newNode() {
        if(!recycled.empty()) {
            int idx = recycled.top();
            recycled.pop();
            return idx;
        }
        parent.push_back(parent.size());
        rank.push_back(1);
        return parent.size()-1;
    }
    
    void deleteNode(int x) {
        parent[x] = x; // 重置状态
        rank[x] = 1;
        recycled.push(x);
    }
};

int find(int x) {
    if(parent[x] != x) {
        // 以50%概率进行路径压缩
        if(rand() % 2 == 0) 
            parent[x] = parent[parent[x]];
        return find(parent[x]);
    }
    return x;
}