并查集的封装操作

为了~~装X~~使我们的代码更加有条理，我们应当用类对一些特定的一组结构进行封装，既然要~~装X~~学习这种操作，那我们就先从最简单的并查集~~开刀~~了解吧！ 先提一下并查集的英文名叫做DisjointSet，亦或是UnionFindSet，支持find，merge两种操作，特定的情境下可以将并查集的功能进行拓展，这里是带路径压缩启发式合并的基础并查集。 不多说，上代码 ------------ [接口] 结构体：DisjointSet 成员变量：vector<int> father; vector<int> rank; 成员函数：find(int v) (O(1)) merge(int x, int y) (O(1)) DisjointSet(int n) (O(n)) ------------ ```cpp class DisjointSet { private: vector<int> father, rank; int n; public: DisjointSet(int n) : father(n+1), rank(n+1) { for(int i = 1; i <= n; ++i) { father[i] = i; } } int find(int v) { return father[v] = v == father[v]? v: find(father[v]); } void merge(int x, int y) { int a = find(x), b = find(y); if(rank[a] < rank[b]) { father[a] = b; } else { father[b] = a; if(rank[b] == rank[a]) { ++rank[a]; } } } }; ```