二級(jí)考試C基礎(chǔ):并查集UFSet類(lèi)

/*
    Name: 并查集UFSet類(lèi)
    Copyright: 始發(fā)于goal00001111的專(zhuān)欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
    Author: goal00001111
    Date: 23-12-08 15:21
    Description: 實(shí)現(xiàn)了普通的查找和合并的算法，也實(shí)現(xiàn)了壓縮路徑和按大小求并高效算法，并對(duì)兩者進(jìn)行了測(cè)試比較。
    有關(guān)算法的分析討論詳見(jiàn)拙作《一種簡(jiǎn)單而有趣的數(shù)據(jù)結(jié)構(gòu)--并查集》：
    */
    #include
    #include
    using namespace std;
    const int MAX = 50000; //集合的成員數(shù)量
    class UFSet{ //并查集類(lèi)
    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); //尋找序號(hào)pos的族長(zhǎng)大人
    bool Unite(int posI, int posJ);//將成員posI和posJ合并到同一個(gè)家族
    int FindFatherAndReducePath(int pos); //查找族長(zhǎng)并壓縮路徑
    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; //返回本對(duì)象的引用
    }
    int UFSet::FindFather(int pos)//尋找序號(hào)pos的族長(zhǎng)大人。若pos本身是族長(zhǎng)，則返回自身
    {
    if (father[pos] < 0)
    return pos;
    return FindFather(father[pos]);
    }
    bool UFSet::Unite(int posI, int posJ)//將成員posI和posJ合并到同一個(gè)家族
    {
    //首先各自去尋找自己的族長(zhǎng)
    int fI = FindFather(posI);
    int fJ = FindFather(posJ);
    if (fI == fJ) //如果是同一個(gè)族長(zhǎng)門(mén)下，不必合并，即合并失敗
    return false;
    else
    father[fJ] = fI; //否則fI當(dāng)族長(zhǎng)：誰(shuí)讓posI站在posJ的前面呢！
    return true;
    }
    int UFSet::FindFatherAndReducePath(int pos)//查找族長(zhǎng)并壓縮路徑
    {
    if (father[pos] < 0)
    return pos;
    //若自己不是族長(zhǎng)，則找到族長(zhǎng)后，將所途經(jīng)的結(jié)點(diǎn)均指向族長(zhǎng)
    return father[pos] = FindFatherAndReducePath(father[pos]);
    }
    bool UFSet::UnionBySize(int posI, int posJ)//按大小求并
    {
    //首先各自去尋找自己的族長(zhǎng)
    int fI = FindFatherAndReducePath(posI);
    int fJ = FindFatherAndReducePath(posJ);
    if (fI == fJ) //如果是同一個(gè)族長(zhǎng)門(mén)下，不必合并，即合并失敗
    return false;
    else if (father[fI] < father[fJ])
    {//如果族長(zhǎng)fI的實(shí)力比f(wàn)J強(qiáng)，即|fI|>|fJ|，則fI當(dāng)族長(zhǎng)，并修改father[fI]和father[fJ]
    father[fI] += father[fJ];
    father[fJ] = fI;
    }
    else //否則fJ當(dāng)族長(zhǎ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    {
    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    {
    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;
    }