IITKESO207SPA3E - Maybe a Minimum Spanning Tree

no tags 

Problem description


Given a connected graph G = (V,E) with non-negative 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


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: 2017-07-09 12:17:11

It should be clear whether graph is directed or undirected....!

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