樹的合并方法

BUPT-BYR 2010-12-20

展開全文

/************************************************/

加權(quán)合并：
每次合并將節(jié)點少的樹嫁接到節(jié)點多的樹的根節(jié)點上；
樹的根處存放節(jié)點個數(shù)的相反數(shù)：
void Fmsets::weighted_merge(int i, int j)
{
if(parent_[i] < parent_[j])
std::swap(i,j);
parent_[j] += parent_[i];
parent_[i] = j; //因為j子樹節(jié)點較多：
}
/*************************************************/
按秩合并：
將秩小的子樹嫁接到秩多的子樹上；
子樹的根處存放子樹的秩相反數(shù)：
void Mfsets::ranked_merge(int i, int j)
{
if(parent_[i] < parent_[j])
swap(i,j);
if(parent_[i] == parent_[j])
--parent_[j];
parent_[i] = j; //因為j的節(jié)點的秩較大；
}
/*********************************************************/
折疊查找：
將被查找的節(jié)點到其根的路徑上的所有節(jié)點都直接嫁接到根節(jié)點上；
int Mfsets::colapsing_find(int i)
{
    int rt = i;
    for( ; parent_[rt] >= 0; rt = parent_[rt]){ }
    for(int temp; rt != i; i = temp) {
        temp = parent_[i];
        parent_[i] = rt;
    }
    return rt;
}
/**********************************************/

按秩合并與折疊查找結(jié)合使用：
struct Fmsets {
    Fmsets(int n) : parent_(n, -1) { }
    int find(int i) { return colapsing_find(i); }
    void merge(int i, int j) { ranked_merge(i, j); }
    bool find_merge(int i, int j) {
        i = find(i); j = find(j);
        if(i == j) return false;
        merge(i, j); return true;
    }
private:
    vector<int> parent_;
protected:
    int colapsing_find(int i)
    { //.é..￡!: i ..
        int rt = i;
        for( ; parent_[rt] >= 0; rt = parent_[rt])
        { }
        for(int temp; rt != i; i = temp)
        { temp = parent_[i]; parent_[i] = rt; }
        return rt;
    }
    void ranked_merge(int i, int j)
    {
        if(parent_[i] < parent_[j])
            swap(i,j);
        if(parent_[i] == parent_[j])
            --parent_[j];
        parent_[i] = j;
    }
}; //~class Fmsets

/*****************************************************/