主要分为两步,find查找 和 union合并
其中在find的过程中可以进行路径的压缩,在union的过程中可以利用size数组统计当前树的节点数,从而实现把节点数少的树合并到节点数多的树
// 初始化vector<int> father(size);void build(int size){for (int i = 0; i < size; ++i){father[i] = i; // 初始化时所有节点的父节点都是自身}}// 查找int find(int x){if (father[x] != x){father[x] = find(father[x]); // 此处起到了路径压缩的作用}return father[x];}// 合并vector<int> size(size, 1); // 用以记录树的节点数void union(int x, int y){int father_x = find(x);int father_y = find(y);if (father_x == father_y) return;if (size[father_x] > size[father_y]){father[father_y] = father_x; // 让节点数少的链接到节点数多的size[father_x] += size[father_y];}else{father[father_x] = father_y;size[father_y] += size[father_x];}}
