Description
For a given weighted graph $G = (V, E)$, find the minimum spanning tree (MST) of $G$ and print the total weight of edges belong to the MST. You may use the code template below and replace /*TODO*/ section with your code.
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
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;
Graph(int V, int E)
{
this->V = V;
this->E = E;
}
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;
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)
{
/*TODO*/
}
// Union by rank
void merge(int x, int y)
{
x = find(x), y = find(y);
/*TODO*/
}
};
/* Functions returns weight of the MST*/
int Graph::kruskalMST()
{
int mst_wt = 0;
// 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++)
{
/*TODO*/
}
return mst_wt;
}
int main()
{
/* Let us create above shown weighted
and undirected graph */
int V = 0, E = 0;
cin >> V >> E;
Graph g(V, E);
for(int i = 0; i < E; i++){
int u, v, w;
cin >> u >> v >> w;
g.addEdge(u, v, w);
}
int mst_wt = g.kruskalMST();
cout << mst_wt << endl;
return 0;
}
Input
The input format is as follows:
|V| |E|
s0 t0 w0
s1 t1 w1
: : :
s|E|−1 t|E|−1 w|E|−1
- |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.
- si and ti represent source and target vertices of i-th edge (undirected) and wi represents the weight of the i-th edge.
Note:
- 1 ≤ |V| ≤ 10,000
- 0 ≤ |E| ≤ 100,000
- 0 ≤ wi ≤ 10,000
- The graph is connected
- There are no parallel edges
- There are no self-loops
Output
Print the total weight of the minimum spanning tree of $G$.
Note: You should append a newline character(`\n`) after the output.
Tags