并查集UFSet类

/*

Name: 并查集UFSet类

Copyright: 始发于goal00001111的专栏；答允自由转载，但必需注明作者和出处

Author: goal00001111

Date: 23-12-08 15:21

Description: 实现了普通的查找和归并的算法，也实现了压缩路径和按巨细求并高效 算法，并对两者举办了测试较量。

有关算法的阐明接头详见拙作《一种简朴而有趣的数据布局–并查集》：

http://blog.csdn.net/goal00001111/archive/2008/12/24/3595844.aspx

*/

#include <iostream>
#include <time.h>
using namespace std;
const int MAX = 50000; //荟萃的最大成员数量
class UFSet{ //并查集类
public:
UFSet(int s = MAX); //结构函数
UFSet(const UFSet & obj); //拷贝结构函数
~UFSet() //析构函数
{
delete []father;
}
UFSet & operator = (const UFSet & obj); //赋值函数
int FindFather(int pos); //寻找序号pos的族长大人
bool Unite(int posI, int posJ);//将成员posI和posJ归并到同一个家属
int FindFatherAndReducePath(int pos); //查找族长并压缩路径
bool UnionBySize (int posI, int posJ); //按巨细求并
bool SameFamily(int posI, int posJ); //判定成员posI和posJ是否属于同一家属
void PrintUFSet();
private:
int *father; //并查集成员数组，存放各元素的父亲结点
int size; //并查集成员数量
};
UFSet::UFSet(int s) : size(s) //结构函数
{
father = new int[size + 1];
for (int i=0; i<=size; i++) //所有的数组元素值均初始化为-1
father[i] = -1;
}
UFSet::UFSet(const UFSet & obj) //拷贝结构函数
{
size = obj.size;
father = new int[size + 1];
for (int i=0; i<=size; i++)
father[i] = obj.father[i];
}
UFSet & UFSet::operator = (const UFSet & obj) //赋值函数
{
if (this == &obj) //查抄自赋值
return *this;
delete []father; //释放原有的内存资源
size = obj.size; //分派新的内存资源，并复制内容
father = new int[size + 1];
for (int i=0; i<=size; i++)
father[i] = obj.father[i];
return *this; //返回本工具的引用
}
int UFSet::FindFather(int pos)//寻找序号pos的族长大人。若pos自己是族长，则返回 自身
{
if (father[pos] < 0)
return pos;
return FindFather(father[pos]);
}
bool UFSet::Unite(int posI, int posJ)//将成员posI和posJ归并到同一个家属
{
//首先各自去寻找本身的族长
int fI = FindFather(posI);
int fJ = FindFather(posJ);
if (fI == fJ) //假如是同一个族长门下，不必归并，即归并失败
return false;
else
father[fJ] = fI; //不然fI当族长：谁让posI站在posJ的前面呢！
return true;
}
int UFSet::FindFatherAndReducePath(int pos)//查找族长并压缩路径
{
if (father[pos] < 0)
return pos;
//若本身不是族长，则找到族长后，将所路过的结点均指向族长
return father[pos] = FindFatherAndReducePath(father[pos]);
}
bool UFSet::UnionBySize(int posI, int posJ)//按巨细求并
{
//首先各自去寻找本身的族长
int fI = FindFatherAndReducePath(posI);
int fJ = FindFatherAndReducePath(posJ);
if (fI == fJ) //假如是同一个族长门下，不必归并，即归并失败
return false;
else if (father[fI] < father[fJ])
{//假如族长fI的实力比fJ强，即|fI|>|fJ|，则fI当族长，并修改father[fI]和 father[fJ]
father[fI] += father[fJ];
father[fJ] = fI;
}
else //不然fJ当族长
{
father[fJ] += father[fI];
father[fI] = fJ;
}
return true;
}
bool UFSet::SameFamily(int posI, int posJ)//判定成员posI和posJ是否属于同一家属
{
return FindFatherAndReducePath(posI) == FindFatherAndReducePath(posJ);
}
void UFSet::PrintUFSet()//输出荟萃的所有元素
{
for (int i=0; i<=size; i++)
cout << father[i] << ' ';
cout << endl;
}
int main()
{
time_t startTime, endTime;
UFSet obj;
int p, q;
time(&startTime);
for (int i=0; i<MAX; i++)
{
p = rand() % MAX + 1;
q = rand() % MAX + 1;
if (p == q)
continue;
//cout << p << "-" << q << " ";
// if (i % 10 == 0)
// cout << endl;
obj.Unite(p, q);
}
while (1)
{
p = rand() % MAX + 1;
q = rand() % MAX + 1;
if (p == q)
continue;
if (obj.SameFamily(p, q))
cout << endl << p << "≡" << q << endl;
else
cout << endl << p << "!≡" << q << endl;
break;
}
time(&endTime);
cout << difftime(endTime, startTime) << endl;
//////////////////////////////////////////////////////////////////////////
time(&startTime);
for (int i=0; i<MAX; i++)
{
p = rand() % MAX + 1;
q = rand() % MAX + 1;
if (p == q)
continue;
//cout << p << "-" << q << " ";
// if (i % 10 == 0)
// cout << endl;
obj.UnionBySize(p, q);
}
while (1)
{
p = rand() % MAX + 1;
q = rand() % MAX + 1;
if (p == q)
continue;
if (obj.SameFamily(p, q))
cout << endl << p << "≡" << q << endl;
else
cout << endl << p << "!≡" << q << endl;
break;
}
time(&endTime);
cout << difftime(endTime, startTime) << endl;
system("pause");
return 0;
}