精品理论电影在线_日韩视频一区二区_一本色道精品久久一区二区三区_香蕉综合视频

　　/*
　　Name: 并查集UFSet類
　　Copyright: 始發(fā)于goal00001111的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
　　Author: goal00001111
　　Date: 23-12-08 15:21
　　Description: 實(shí)現(xiàn)了普通的查找和合并的算法，也實(shí)現(xiàn)了壓縮路徑和按大小求并高效算法，并對兩者進(jìn)行了測試比較。
　　有關(guān)算法的分析討論詳見拙作《一種簡單而有趣的數(shù)據(jù)結(jié)構(gòu)--并查集》：
　　*/
　　#include <iostream>
　　#include <time.h>
　　using namespace std;
　　const int MAX = 50000; //集合的最大成員數(shù)量
　　class UFSet{ //并查集類
　　public:
　　UFSet(int s = MAX); //構(gòu)造函數(shù)
　　UFSet(const UFSet & obj); //拷貝構(gòu)造函數(shù)
　　~UFSet() //析構(gòu)函數(shù)
　　{
　　delete []father;
　　}
　　UFSet & operator = (const UFSet & obj); //賦值函數(shù)
　　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; //并查集成員數(shù)組，存放各元素的父親結(jié)點(diǎn)
　　int size; //并查集成員數(shù)量
　　};
　　UFSet::UFSet(int s) : size(s) //構(gòu)造函數(shù)
　　{
　　father = new int[size + 1];
　　for (int i=0; i<=size; i++) //所有的數(shù)組元素值均初始化為-1
　　father[i] = -1;
　　}
　　UFSet::UFSet(const UFSet & obj) //拷貝構(gòu)造函數(shù)
　　{
　　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) //賦值函數(shù)
　　{
　　if (this == &obj) //檢查自賦值
　　return *this;
　　delete []father; //釋放原有的內(nèi)存資源
　　size = obj.size; //分配新的內(nèi)存資源，并復(fù)制內(nèi)容
　　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當(dāng)族長：誰讓posI站在posJ的前面呢！
　　return true;
　　}
　　int UFSet::FindFatherAndReducePath(int pos)//查找族長并壓縮路徑
　　{
　　if (father[pos] < 0)
　　return pos;
　　//若自己不是族長，則找到族長后，將所途經(jīng)的結(jié)點(diǎn)均指向族長
　　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的實(shí)力比fJ強(qiáng)，即|fI|>|fJ|，則fI當(dāng)族長，并修改father[fI]和father[fJ]
　　father[fI] += father[fJ];
　　father[fJ] = fI;
　　}
　　else //否則fJ當(dāng)族長
　　{
　　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;
　　}