백준 1774번 우주신과의 교감(C++)

모든 간선간의 거리를 구해서 작은순으로 정렬하고

이미 연결된 수 제외하고 n-v-1개까지 유니온시키기 

좌표간 연결은 순번 을 부여해서 사용하면 된다. 

#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<tuple>

using namespace std;

typedef tuple<double,int,int>tp;
vector<int>parent;

vector<pair<double,double>>num;

double distance(double x1,double y1,double x2,double y2){
    
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}


int find(int node){
    if(parent[node]<0)return node;
    return parent[node]=find(parent[node]);
}


bool unions(int x,int y){
    
    int xp=find(x);
    int yp=find(y);
    
    if(xp==yp)return false; 
    
    if(parent[xp]<parent[yp]){
        parent[xp]+=parent[yp];
        parent[yp]=xp;
    }
    else{
        parent[yp]+=parent[xp];
        parent[xp]=yp;
    }
    return true; 
}

//priority_queue<tp, vector<tp>, greater<>> pq;

int main(){
    
    int n,m;
    
    cin>>n>>m;
    double x,y;
    parent.assign(n+1,-1);
    
    num.assign(n+1,{0,0});
    
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        num[i]={x,y}; 
    }
    
   int a,b;
   int v=0;
    //이미 연결 
    for(int j=0;j<m;j++){
        cin>>a>>b;
        if(unions(a,b)){
            v++;
        
        }
    }
    
    //거리 계산하고 작은 거리부터 
    priority_queue<tp,vector<tp>,greater<tp>>pq;
    
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            double dist=distance(num[i].first,num[i].second,num[j].first,num[j].second);
            pq.push({dist,i,j});
       
        }
    }
    
   
    double sum=0; 
    int cnt=0;
    
    while(cnt<n-v-1){ //?
        
        double w=get<0>(pq.top());
        int x=get<1>(pq.top());
        int y=get<2>(pq.top());
        
        pq.pop();
        
        if(unions(x,y)){
            cnt++;
            sum+=w; 
        }
       
    }
    
    
    
    cout<<fixed;
    cout.precision(2);
    cout<<sum;
    
    
    
    return 0; 
}