Kruskal's Minimum Spanning Tree using STL in C++

// C++ program for Kruskal's algorithm to find Minimum // Spanning Tree of a given connected, undirected and // weighted graph #include<bits/stdc++.h> using namespace std; // Creating shortcut for an integer pair typedef pair<int, int> iPair; // Structure to represent a graph struct Graph {  int V, E;  vector< pair<int, iPair> > edges;  // Constructor  Graph(int V, int E)  {  this->V = V;  this->E = E;  }  // Utility function to add an edge  void addEdge(int u, int v, int w)  {  edges.push_back({w, {u, v}});  }  // Function to find MST using Kruskal's  // MST algorithm  int kruskalMST(); }; // To represent Disjoint Sets struct DisjointSets {  int *parent, *rnk;  int n;  // Constructor.  DisjointSets(int n)  {  // Allocate memory  this->n = n;  parent = new int[n+1];  rnk = new int[n+1];  // Initially, all vertices are in  // different sets and have rank 0.  for (int i = 0; i <= n; i++)  {  rnk[i] = 0;  //every element is parent of itself  parent[i] = i;  }  }  // Find the parent of a node 'u'  // Path Compression  int find(int u)  {  /* Make the parent of the nodes in the path  from u--> parent[u] point to parent[u] */  if (u != parent[u])  parent[u] = find(parent[u]);  return parent[u];  }  // Union by rank  void merge(int x, int y)  {  x = find(x), y = find(y);  /* Make tree with smaller height  a subtree of the other tree */  if (rnk[x] > rnk[y])  parent[y] = x;  else // If rnk[x] <= rnk[y]  parent[x] = y;  if (rnk[x] == rnk[y])  rnk[y]++;  } }; /* Functions returns weight of the MST*/ int Graph::kruskalMST() {  int mst_wt = 0; // Initialize result  // Sort edges in increasing order on basis of cost  sort(edges.begin(), edges.end());  // Create disjoint sets  DisjointSets ds(V);  // Iterate through all sorted edges  vector< pair<int, iPair> >::iterator it;  for (it=edges.begin(); it!=edges.end(); it++)  {  int u = it->second.first;  int v = it->second.second;  int set_u = ds.find(u);  int set_v = ds.find(v);  // Check if the selected edge is creating  // a cycle or not (Cycle is created if u  // and v belong to same set)  if (set_u != set_v)  {  // Current edge will be in the MST  // so print it  cout << u << " - " << v << endl;  // Update MST weight  mst_wt += it->first;  // Merge two sets  ds.merge(set_u, set_v);  }  }  return mst_wt; } // Driver program to test above functions int main() {  /* Let us create above shown weighted  and undirected graph */  int V = 9, E = 14;  Graph g(V, E);  // making above shown graph  g.addEdge(0, 1, 4);  g.addEdge(0, 7, 8);  g.addEdge(1, 2, 8);  g.addEdge(1, 7, 11);  g.addEdge(2, 3, 7);  g.addEdge(2, 8, 2);  g.addEdge(2, 5, 4);  g.addEdge(3, 4, 9);  g.addEdge(3, 5, 14);  g.addEdge(4, 5, 10);  g.addEdge(5, 6, 2);  g.addEdge(6, 7, 1);  g.addEdge(6, 8, 6);  g.addEdge(7, 8, 7);  cout << "Edges of MST are \n";  int mst_wt = g.kruskalMST();  cout << "\nWeight of MST is " << mst_wt;  return 0; }