C++에서 분리 세트 구현

Question

온라인 컨테스트에서이 문제가 발생했으며 분리형 데이터 구조를 사용하여이 문제를 해결하려고합니다.

문제 정의 :

밥은 자신의 수학 여행 동안 원자력 발전소를 방문. 그는 식물 안에 핵폭탄이 없다고보고 핵폭탄의 초기 효율은 1입니다. 일정 기간이 지나면 핵 봉이 서로 융합하여 결합하여 한 그룹을 형성합니다. 이 과정은 핵폭탄의 효율을 그룹 크기의 제곱근으로 줄인다. 호기심 많은 학생 인 Bob은 잠시 후 원자력 발전소의 총 효율을 알고 싶어합니다. 이것은 그룹의 효율성을 더함으로써 얻어진다.

처음에는 모든 막대가 크기 1의 자체 그룹에 속합니다. f 융합이 있습니다. rod1과 rod2가 융합되면 그룹이 융합되었음을 의미합니다.

시료 입력 :

5 2

1 2

2 3

샘플 출력 :

,691,363,210

3.73

설명 :

N = 5 융합체 = 2

기 1,2,3 => 1.73 (SQRT (3))

그룹 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. 
} 

위의 코드는 모든을 testcases하지만 하나 작동하는 것 같다.

코드 입력에 실패한 입력은 here입니다.

예상 출력은 다음과 같습니다 67484.82

내 출력 : 입력이 정말 큰이기 때문에 내가 잘못 어디로 갔는지 67912.32

정말 해결할 수 없습니다.

도움이 될만한 의견이 있습니다. 미리 감사드립니다.

Answer 1

p에는 findSet 값이 아닌 요소의 직계 부모가 있습니다. 따라서 set<lli> s (p.begin(),p.end());을 수행 할 때 추가 요소가있을 수 있습니다.

이 다루는 내가 생각할 수있는 두 가지 방법이 있습니다 : 대신에 당신이 setSize[i] += setSize[j]을 한 후 직접

을 P 퍼팅의 루프

1. 삽입 findSet (ⅰ) 세트로, setSize[j] = 0을 설정합니다. 이렇게하면 중급 부모는 합계에 기여하지 않습니다.