IITKESO207SPA3E - Maybe a Minimum Spanning Tree
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
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
ahmdalgendi:
2018-10-05 11:25:58
why i can t submit my solution |
|
daud_spoj2015:
2017-07-09 12:17:11
It should be clear whether graph is directed or undirected....!
|
Added by: | Programming Club, IITK |
Date: | 2017-07-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | ESO207, IIT Kanpur Summer Semester 2017 |