IITKESO207SPA3E  Maybe a Minimum Spanning Tree
Problem description
Given a connected graph G = (V,E) with nonnegative edge weights, here is a different way to construct an MST greedily by deleting edges instead of adding edges. The basic idea is as follows :
 E' = E
 Repeat
Pick any cycle in G, find the heaviest edge, delete it from the set E'
Until E' is an MST.
You have to conver the basic diea into a proper algorithm.
Input format
The input will have in one line, an integer n. This will represent the number of nodes in the tree. The remaining lines will denote the edges in the graph, one edge per each line. The format of the edges will be of the form i j w, three space separated integers denoting the start vertex, the end vertex, and the edge weight of the edge.
Output format
Your output must contain all the edges in your MST created using the above algorithm . It must have one edge per line, ordered in increasing order of the first node, then the second node.
Sample Input
9
1 2 5
2 3 3
1 5 1
2 4 2
4 5 6
9 8 1
5 7 7
1 6 3
8 6 5
9 5 4
Sample Output
1 2
1 5
1 6
2 3
2 4
5 7
5 9
8 9
Note 1 : The test case had a flaw in it, which caused many students to obtain 80/100. It has been updated since then, please resubmit your solutions.
hide comments
daud_spoj2015:
20170709 12:17:11
It should be clear whether graph is directed or undirected....!

Added by:  Programming Club, IITK 
Date:  20170706 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ESO207, IIT Kanpur Summer Semester 2017 