SHARE
TWEET

Untitled

a guest Nov 19th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct edge{
  5.  
  6. int p,k,d;
  7.  
  8. };
  9. int par[100];
  10. int makeset(int k)
  11. {
  12.     par[k]=k;
  13. }
  14.  
  15. int fin(int a)
  16. {
  17.     if(par[a]=a)
  18.     {
  19.         return a;
  20.     }
  21.     else
  22.     {
  23.        return par[a]=fin(par[a]) ;
  24.     }
  25. }
  26.  
  27. int uni( int a,int b)
  28. {
  29.     int u;
  30.     int v;
  31.  
  32.  
  33.  
  34.     u=fin( a);
  35.     v=fin( b);
  36.     if(u==v)
  37.     {
  38.         return 0;
  39.     }
  40.     else if(u!=v)
  41.     {
  42.          return 1;
  43.         par[v]=u;
  44.  
  45.  
  46.  
  47.     }
  48.  
  49. }
  50.  
  51. int main()
  52. {
  53.      int n,e;
  54.     cin>>n>>e;
  55.     struct edge edges[e];
  56.  
  57.     for(int i=1;i<=n;i++)
  58.     {
  59.        makeset(i);
  60.     }
  61. int x,y,z,cost=0,cnt=0;
  62. for(int i=0;i<e;i++)
  63. {
  64.    cin>>edges[i].p;
  65.    cin>>edges[i].k;
  66.    cin>>edges[i].d;
  67.  
  68.  
  69. }
  70. for(int i=0;i<e;i++)
  71. {
  72.     for(int j=0;j<e-1;j++)
  73.     {
  74.         if(edges[j].d>edges[j+1].d)
  75.         {
  76.             swap(edges[j],edges[j+1]);
  77.         }
  78.     }
  79. }
  80.  
  81. cout<<"sorted edges"<<endl;
  82. for(int i=0;i<e;i++)
  83. {
  84.     cout<<edges[i].p<<" "<<edges[i].k<<" "<<edges[i].d<<endl;
  85.  
  86. }
  87.  
  88.  
  89.  
  90. for(int i=0;i<e;i++)
  91.  
  92. {
  93.     int l=uni(edges[i].p,edges[i].k);
  94.     if(l==1)
  95.     {
  96.          cost=cost+edges[i].d;
  97.     }
  98.  
  99. }
  100.  cout<<cost<<endl;
  101.  
  102.  
  103. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top