基本概念

class UnionFind{
public:// 查找祖先：如果节点的父节点不为空，那就不断迭代。int find(int x){int root = x;while(father[root] != -1){root = father[root];}// 路径压缩while(x != root){int original_father = father[x];father[x] = root;x = original_father;}return root;}// 判断两个节点的连通性bool is_connected(int x,int y){return find(x) == find(y);}// 合并两个节点：如果发现两个节点是连通的，// 那么就要把他们合并，也就是他们的祖先是相同的。// 这里究竟把谁当做父节点一般是没有区别的。void Union(int x,int y){int root_x = find(x);int root_y = find(y);if(root_x != root_y){father[root_x] = root_y;num_of_sets--;}}// 初始化：当把一个新节点添加到并查集中，它的父节点应该为空void add(int x){if(!father.count(x)){father[x] = -1;num_of_sets++;}}int get_num_of_sets(){return num_of_sets;}private:// 记录父节点unordered_map<int,int> father;// 记录集合数量int num_of_sets = 0;
};