并查集

以下是并查集模板，核心数据结构是一个哈希表,(k,v)表示键以及该键的根结点，新key插入节点调用add函数在哈希表中插入（key,-1），寻找根节点是find函数，merge函数将两个树的根节点合并

class UnionFind{
public:
    // 记录父节点
    unordered_map<int,int> father;
    void add(int x){
        if(!father.count(x)){
            father[x] = -1;
        }
    }
    int find(int x){
        int root = x;
        while(father[root] != -1){
            root = father[root];
        }
        return root;
    }
    bool is_connected(int x,int y){
        return find(x) == find(y);
    }
    void merge(int x,int y){
        int root_x = find(x);
        int root_y = find(y);
        if(root_x != root_y){
            father[root_x] = root_y;
        }
    }
};