并查集(路径压缩)C++实现

class UnionFind { private: int *father; int count; public: UnionFind(int n) { this->count = n; father = new int[n]; for (int i=0; i<n; ++i) father[i] = i; } ~UnionFind(int n) { delete[] father; } // 查找索引为x的节点的父亲节点的索引 int find(int x) { assert(x >= 0 && x < count); int a = x; while (x != father[x]) x = father[x]; while (a != father[a]) { int z = a; a = father[a]; father[z] = x; } return x; } void Union(int x, int y) { int fx = find(x); int fy = find(y); if (fx != fy) father[fx] = fy; } bool isConnected(int x, int y) { return find(x) == find(y); } };