Facebook
From kru, 1 Week ago, written in C++.
Embed
Download Paste or View Raw
Hits: 162
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<vector<int>> adj;
  4. vector<int> parent;
  5. vector<int> Rank;
  6. int n=4;
  7. void addEdge(int i, int j, int w)
  8. {
  9.     adj.push_back({w,i,j});
  10. }
  11. void makeSet()
  12. {
  13.     parent.resize(n);
  14.     Rank.resize(n);
  15.     for(int i=0; i<n; i++)
  16.     {
  17.         parent[i]=-1;
  18.         Rank[i]=1;
  19.     }
  20. }
  21. int find(int i)
  22. {
  23.     if(parent[i]==-1) return i;
  24.     else return parent[i]=find(parent[i]);
  25. }
  26. void Union(int i, int j)
  27. {
  28.     int s1 = find(i);
  29.     int s2 = find(j);
  30.     if(s1!=s2)
  31.     {
  32.         if(Rank[s1]<Rank[s2])
  33.         {
  34.             parent[s1]=s2;
  35.             Rank[s2]+=Rank[s1];
  36.         }
  37.         else
  38.         {
  39.             parent[s2]=s1;
  40.             Rank[s1]+=Rank[s2];
  41.         }
  42.     }
  43. }
  44. void kruskal()
  45. {
  46.     makeSet();
  47.     sort(adj.begin(), adj.end());
  48.     int cost=0;
  49.     for(auto edge:adj)
  50.     {
  51.         int wt=edge[0];
  52.         int i=edge[1];
  53.         int j=edge[2];
  54.         int s1=find(i);
  55.         int s2=find(j);
  56.         if(s1!=s2)
  57.         {
  58.             Union(s1,s2);
  59.             cost+=wt;
  60.         }
  61.     }
  62.     cout<<cost<<endl;
  63. }
  64. int main()
  65. {
  66.     addEdge(0,1,1);
  67.  addEdge(1,3,3);
  68.  addEdge(3,2,4);
  69.  addEdge(2,0,2);
  70.  addEdge(0,3,2);
  71.  addEdge(1,2,2);
  72.     kruskal();
  73. }