这篇比较简单，看看书就会了，需要注意的是这里使用静态数组实现的集合的，而且默认数组的下标即为存储的集合元素。
UnionFindSet.h
#pragma once
#ifndef UNIONFINDSET_H
#define UNIONFINDSET_H
#include<iostream>
using std::swap;
using std::cout;
using std::endl;//并查集类
class UnionFindSet
{
public:UnionFindSet(int sz);//初始化并查集父节点数组~UnionFindSet();void GenerentSet(int a[], int number, int parent);//生成一个父节点为root，且有number个数量的子节点的集合int Find(int val);//搜索元素val所在的setvoid Merge(int root1, int root2);//如果两个集合不重叠，就把集合root2并入root1中void WeightenMerge(int root1, int root2);//加权融合两个集合，将节点多的融合进节点少的void PrintParent();
private:int size;int* parent;
};UnionFindSet::UnionFindSet(int sz)
{parent = new int[sz];if (parent == nullptr) { exit(-1); }size = sz;for (int i = 0; i < size; i++)//默认并查集的每个元素的父节点都为-1parent[i] = -1;
}UnionFindSet::~UnionFindSet()
{if (parent) delete[]parent;
}//生成一个父节点为root，且有number个数量的子节点的集合
void UnionFindSet::GenerentSet(int a[], int number, int root)
{for (int i = 0; i < number; i++)parent[a[i]] = root;
}//搜索元素val所在的set
int UnionFindSet::Find(int val)
{if (parent[val] < 0) return val;else return Find(parent[val]);//while (parent[val] > 0)// val = parent[val];//return val;
}//如果两个集合不重叠，就把集合root2并入root1中
void UnionFindSet::Merge(int root1, int root2)
{for (int i = 0; i < size; i++){if (root1 == parent[i]){parent[root2] = i;return;}}
}//加权融合两个集合，将节点多的融合进节点少的
void UnionFindSet::WeightenMerge(int root1, int root2)
{int num1 = 0, num2 = 0;for (int i = 0; i < size; i++) //统计两个集合拥有的节点数量{int x;if (parent[i] > 0) x = Find(parent[i]);else x = i;if (x == root1) num1++;if (x == root2) num2++;}if (num1 < num2) { swap(root1, root2); }//如果num1小于num2，交换root1与root2的值，因为我们需要调用Merge函数Merge(root1, root2);
}void UnionFindSet::PrintParent()
{for (int i = 0; i < size; i++)cout << parent[i] << " ";cout << endl;
}#endif // !UNIONFINDSET_H
main.cpp
#include"UnionFindSet.h"int main()
{UnionFindSet myset(10);int a[] = { 3,4,5 };int b[] = { 6,7 };int c[] = { 8,9 };myset.GenerentSet(a, 3, 0);myset.GenerentSet(b, 2, 1);myset.GenerentSet(c, 2, 2);myset.PrintParent();myset.Merge(0, 1);myset.PrintParent();myset.WeightenMerge(0, 2);myset.PrintParent();return 1;
}