union find算法 c++

1.原理参考

labuladong-fucking-algorithm/算法思维系列/UnionFind算法详解.md at master · jiajunhua/labuladong-fucking-algorithm · GitHub

2.初级模式

#include <iostream>class UF {public:// 记录连通分量/* 构造函数，n 为图的节点总数 */UF(int n) {count = n;//    int arr[n];parent_arr = new int[n]; for(int i=0; i<n; i++){parent_arr[i] = i;}};/* 其他函数 */~UF(){delete[] parent_arr;}void union_func(int p, int q);int find(int x);int getCount();bool connect(int p, int q);private:int count;// 节点 x 的节点是 parent[x]//  int[] parent;int* parent_arr; };void UF::union_func(int p, int q)
{int rootP = find(p);int rootQ = find(q);if(rootQ == rootP)return;parent_arr[rootQ] = rootP;count--;}int UF::find(int x)
{while (parent_arr[x] != x){x = parent_arr[x];}return x;
}int UF::getCount()
{return count;
}bool UF::connect(int p, int q)
{int rootP = find(p);int rootQ = find(q);return rootP == rootQ;
}int main()
{UF union_find(7);union_find.union_func(0, 1);union_find.union_func(0, 2);union_find.union_func(0, 3);union_find.union_func(2, 4);union_find.union_func(2, 5);union_find.union_func(3, 6);std::cout << union_find.getCount() << std::endl;return 0;
}

3. 进阶模式

   3.1 平衡性优化 

   3.2  路径压缩

#include <iostream>class UF {public:// 记录连通分量/* 构造函数，n 为图的节点总数 */UF(int n) {count = n;//    int arr[n];parent_arr = new int[n]; size_arr = new int[n];for(int i=0; i<n; i++){parent_arr[i] = i;size_arr[i] = i;}};/* 其他函数 */~UF(){delete[] parent_arr;}void union_func(int p, int q);int find(int x);int getCount();bool connect(int p, int q);private:int count;int* parent_arr;int* size_arr; };void UF::union_func(int p, int q)
{int rootP = find(p);int rootQ = find(q);// 小树接到大树下面，较平衡if (size_arr[rootP] > size_arr[rootQ]) {parent_arr[rootQ] = rootP;size_arr[rootP] += size_arr[rootQ];} else {parent_arr[rootP] = rootQ;size_arr[rootQ] += size_arr[rootP];}count--;}int UF::find(int x)
{while (parent_arr[x] != x){// 进行路径压缩parent_arr[x] = parent_arr[parent_arr[x]];x = parent_arr[x];}return x;
}int UF::getCount()
{return count;
}bool UF::connect(int p, int q)
{int rootP = find(p);int rootQ = find(q);return rootP == rootQ;
}int main()
{UF union_find(7);union_find.union_func(0, 1);union_find.union_func(0, 2);union_find.union_func(0, 3);union_find.union_func(2, 4);union_find.union_func(2, 5);union_find.union_func(3, 6);std::cout << union_find.getCount() << std::endl;return 0;
}