C++ 中的不相交集实现

Question

我在一次在线竞赛中遇到了这个问题，我正在尝试使用不相交集数据结构来解决它。

问题定义：

Bob visits a nuclear power plant during his school excursion. He observes that there are n nuclear rods in the plant and the initial efficiency of the nuclear rods is 1. After a period of time nuclear rods start fusing with each other and combine to form a group. This process reduces the efficiency of the nuclear rods to square root of the size of the group. Bob, being a curious student, wants to know the total efficiency of the nuclear plant after some time. This is obtained by adding the efficiencies of the groups.

Initially all the rods belong to its own group of size 1. There are f fusions. If rod1 and rod2 get fused, it means their groups got fused.

示例输入：

5 2

1 2

2 3

示例输出：

3.73

解释：

n=5 fusions=2

group 1,2,3 => 1.73 (sqrt(3))

group 4 => 1

group 5 => 1

total = (1.73 + 1 + 1) = 3.73

我的代码：

#include <iostream>
#include <set>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <iomanip>
using namespace std;

typedef long long int lli;

vector<lli> p,rank1,setSize;   /* p keeps track of the parent
                                * rank1 keeps track of the rank
                                * setSize keeps track of the size of the set. 
                                */ 

lli findSet(lli i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); } 

bool sameSet(lli x,lli y) { return findSet(x) == findSet(y); }


void union1(lli x,lli y) {      // union merges two sets.

    if(!sameSet(x,y)) {

        lli i = findSet(x), j = findSet(y);

        if(rank1[i] > rank1[j]) {
            p[j] = i;
            setSize[i] += setSize[j];           

        }

        else {
            p[i] = j;
            setSize[j] += setSize[i];
            if(rank1[i] == rank1[j])
                rank1[j]++;
        }
    }
}

int main() {

    freopen("input","r",stdin);

    lli n;
    cin >> n;                               //number of nuclear rods

    setSize.assign(n,1);                    //Initialize the setSize with 1 because every element is in its own set
    p.assign(n,0);          
    rank1.assign(n,0);                      //Initialize ranks with 0's.

    for(lli i = 0; i < n; i++) p[i] = i;    //Every set is distinct. Thus it is its own parent.

    lli f;
    cin >> f;                               //Number of fusions.

    while(f--){                 

        lli x,y;
        cin >> x >> y;                      //combine two rods
        union1(x,y);                        

    }   

    double ans; 

    set<lli> s (p.begin(),p.end());         //Get the representative of all the sets.

    for(lli i : s){     
        ans += sqrt(setSize[i]);            //sum the sqrt of all the members of that set.

    }

    printf("\n%.2f", ans);                  //display the answer in 2 decimal places.
}

上面的代码似乎适用于除一个以外的所有测试用例。

输入是 here，我的代码对此失败了。

预期输出为：67484.82

我的输出：67912.32

我真的不知道哪里出了问题，因为输入量实在是太大了。

任何帮助将不胜感激。提前致谢。

Answer 1

p 保留元素的直接 parents 而不是它们的 findSet 值。因此，当您执行 set<lli> s (p.begin(),p.end()); 时，您可以在那里添加其他元素。

我可以想到两种方法来处理这个问题：

用循环将findSet(i)插入集合中而不是直接把p
完成 setSize[i] += setSize[j] 后，设置 setSize[j] = 0。这样中间的parents就不会对总和有贡献了。

C++ 中的不相交集实现

Disjoint Set implementation in C++

c++

algorithm

disjoint-sets