MST Kruskal 's 알고리즘 (Timelimit)

Question

그래서 과제가 있었고 코드를 작성할 수 있었지만 큰 숫자로는 너무 느리고 어쩌면 내가 개선하도록 도울 수 있습니다. 시간은 3 초입니다. 나는 몇 가지 아이디어를 듣고 싶다. 이 할당에서 최소 스패닝 트리를 찾아야합니다.

입력이 될 것이다 :

1. number of testcases, 
    2. number of nodes, 
    3. a number that says how long can tha longest edge be, 
    4. all the coordinates of the nodes 

다음 출력은 최소이어야한다. MST가없는 경우 출력은 -1이어야합니다.

여기 예입니다 :

Input: 
    1  //number of testcases 
    6 5 //number of nodes, max. length of an edge 
    3 6 //x-,y-coordinates 
    4 7 
    8 1 
    4 4 
    2 7 
    3 3 

    Output: 
    11 

여기에 코드입니다 : 당신은 현재의 가장자리에 두 정점 사건이 동일한 구성 요소에 속해 있는지 파악하기 위해 union-find algorithm을 구현 한

#include<iostream> 
#include<cstdio> 
#include<string> 
#include<algorithm> 
#include<deque> 
#include<vector> 
#include<cmath> 
#include<cstdlib> 

using namespace std; 

#define edge pair<int,int>//format (w,(u,v)) 
          //(weights, (node,node)) 
deque<pair<double,edge> > G,MST; 
deque<int> parent(1000); 
int N,E,diff; 
int total; 
double sum; 
deque<int> X,Y; 

int findset(int x,deque<int>parent){ 
    if(x!=parent[x]) 
     parent[x]=findset(parent[x],parent); 
    return parent[x];      
}                  

int Kruskal(){ 
    for(int i1=0;i1<N;i1++){ //calculate distance between each node 
     for(int j1=i1;j1<N;j1++){ 
      int A,B; 
      double C; 
      A=((X[i1]-X[j1])*(X[i1]-X[j1])); 
      B=((Y[i1]-Y[j1])*(Y[i1]-Y[j1])); 
      C=sqrt(A+B); 
      G.push_back(pair<double,edge>(C,edge(i1,j1))); 
     } 
    } 

    E=G.size();//how many edges 
    int i,pu,pv; 
    sum=0; 
    stable_sort(G.begin(),G.end()); 
    for (i=total=0;i<E;i++){ 
     pu=findset(G[i].second.first, parent); 
     pv=findset(G[i].second.second, parent); 
     if(pu!=pv){ 
      MST.push_back(G[i]); 
      total+=G[i].first; 
      sum+=G[i].first; 

      if(G[i].first>diff) 
       return -1; 
      parent[pu]=parent[pv]; 
     } 
    } 
    return 0; 
} 

int main(){ 
    int t,nodes; 
    double w; 
    diff=0; 
    for(cin>>t ; t>0 ; t--){ 
     N=0; 
     diff=0; 
     X.clear(); 
     Y.clear(); 
     MST.clear(); 
     G.clear(); 
     X.resize(0); 
     Y.resize(0); 

     cin>>N; //how many nodes 
     for(int i=0; i<N; i++) 
      parent[i]=i; 
     cin>>diff; 
     nodes=N; 

     for(nodes; nodes>0;nodes--){  //coordinates of nodes 
      int x,y; 
      cin>>x; 
      X.push_back(x); 
      cin>>y; 
      Y.push_back(y); 
     } 

     int a=0; 
     if(Kruskal()==0){ 
      a=sum; 
      cout<<a<<endl; 
     } 
     else 
      cout<<-1<<endl;   
    } 
    system("pause"); 
    return 0;          
} 

Answer 1

. 그러나 "유니온"을 수행하는 방식은 요소에서 루트까지의 선형 경로로 이어질 수 있습니다. 이를 방지하기위한 적절한 방법은 더 작은 서브 트리를 큰 서브 트리에 첨부하는 것입니다. 그러나 단지 무작위로 (균일)

parent[pu]=parent[pv]; 

또는

parent[pv]=parent[pu]; 

트릭을해야 하나 어떻게 결정.