Question

C++ programing question22

Minimum spanning tree

Time limit: 1 second

Problem Description
For a connected undirected graph G = (V, E), edge e corresponds to a weight w, a minimum weight spaning tree can be found on the graph.
Into trees.
Input file format
At the beginning, there will be a positive integer T, which means that there will be T input data.
The first line of each input has two positive integers n,m, representing n points and m edges on the graph, 2?n?10000, 1?m?
500000, each point is numbered 0~n-1.
Next m rows of the input data has three positive integers U, V, and W, which represent that there is a edge between the u v and the weight is W10000.
Output format
Each line output the sum of the weights of all edges on the minimum spanning tree for each input data.

Example Sample Input Sample Output 5 013 02 3 03 1 13 1

Answer 1

Solution:- I'm going to paste the code that is running on my Local PC just Fine,

=============CODE BEGINS===============

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define edge pair<int,int>

class Graph {
private:
vector<pair<int, edge> > G; // graph
vector<pair<int, edge> > T; // mst
int *parent;
int V; // number of vertices/nodes in graph
public:
Graph(int V);
void AddWeightedEdge(int u, int v, int w);
int find_set(int i);
void union_set(int u, int v);
void kruskal();
int print();
};
Graph::Graph(int V) {
parent = new int[V];

//i 0 1 2 3 4 5
//parent[i] 0 1 2 3 4 5
for (int i = 0; i < V; i++)
parent[i] = i;

G.clear();
T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
// If i is the parent of itself
if (i == parent[i])
return i;
else
// Else if i is not the parent of itself
// Then i is not the representative of his set,
// so we recursively call Find on its parent
return find_set(parent[i]);
}

void Graph::union_set(int u, int v) {
parent[u] = parent[v];
}
void Graph::kruskal() {
int i, uRep, vRep;
sort(G.begin(), G.end()); // increasing weight
for (i = 0; i < G.size(); i++) {
uRep = find_set(G[i].second.first);
vRep = find_set(G[i].second.second);
if (uRep != vRep) {
T.push_back(G[i]); // add to tree
union_set(uRep, vRep);
}
}
}
int Graph::print() {
int ans = 0;
for (int i = 0; i < T.size(); i++) {
ans += T[i].first;
}
return ans;
}
int main() {
int tc, u, v;
int src, dest, wt;
cin>>tc;
while(tc--) {
cin>>u>>v;
Graph g(u);
for (int i = 0; i < v; ++i)
{
cin>>src>>dest>>wt;
g.AddWeightedEdge(src, dest, wt);
}
g.kruskal();
cout<<g.print()<<endl;
}
  
return 0;
}

================CODE ENDS===================

Screenshots:-

Output:-

=============SOLUTION ENDS===================

Note:- Please upvote if it helped, else do comment on the part you didn't like, i'll be happy to help.

Thanks!!