C++でのディスジョイントセットの実装

Question

オンラインコンテストでこの問題が発生しました。私は、ディスジョイントセットデータ構造を使用してこの問題を解決しようとしています。

問題定義：

ボブは修学旅行中に原子力発電所を訪問します。彼は植物に核ロッドがないことを観察し、核ロッドの初期効率は1である。ある期間の後、核ロッドは互いに融合し始め、グループを形成する。このプロセスは、核ロッドの効率をグループの大きさの平方根に減少させる。奇妙な学生であるボブは、しばらくして原子力発電所の総合効率を知りたいと考えています。これは、グループの効率を加えることによって得られる。

最初は、すべてのロッドがサイズ1の独自のグループに属しています.f融合があります。もし、rod1とrod2が融合すると、それらのグループが融合したことを意味します。

サンプル入力：

出力例：

3.73

説明：

N = = 2

グループ1,2,3 => 1.73（SQRT（3））

5つの融合

グループ4 => 1

グループ5 => 1

合計=（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. 
} 

上記のコードは、すべてのテストケースが、1つのために働くように思われます。

入力がhereであり、そのためにコードが失敗します。

予想される出力は次のようになります。67484.82

マイ出力：67912.32

入力が本当に巨大であるため、私が間違っていたところ、私は本当にうまくできません。

本当にありがとうございます。前もって感謝します。

Answer 1

pは、要素の直後の親を保持し、その値はfindSetではありません。したがって、あなたがset<lli> s (p.begin(),p.end());をするときに、そこに追加の要素を持つことができます。

私はこれに対処するための考えることができる2つの方法があります。

1. 挿入findSet（i）が代わりにあなたがsetSize[i] += setSize[j]を実行した後、直接P
2. を置くのループとのセットには、setSize[j] = 0を設定します。この方法では、中間の親は合計に貢献しません。