Minimum Spanning Tree

Submit

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Given a graph, find its minimum spanning tree.

INPUT:
A graph is given as a list of edges.
An edge is specified by three values in a line: vertex1 vertex2 weight.
Vertex1 and vertex2 are given as strings including no spaces, while weight is given as an integer.

OUTPUT:
Print out the sorted list of edges with flags, in ascending order of weights.
Each edge must be specified with four values in a line: use-flag vertex1 vertex2 weight.
Use-flag must be T if the edge is used in the minimum spanning tree. Otherwise it must be F.
Vertex1, vertex2 and weight are the same as the input.

NOTE:
The answer is unique since there is no pair of edges that have the same weight.

References:
http://en.wikipedia.org/wiki/Minimum_spanning_tree
http://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Options

exec is denied

now post-mortem time, all source codes will be revealed

Sample input:_

a l 10
a v 83
b e 32
b i 77
b q 50
c e 80
c g 13
c p 69
c t 117
c x 73
d e 14
d g 113
d q 1
d v 24
e g 37
e r 20
e u 40
e x 115
f t 88
f u 11
f y 95
g i 59
g y 107
g z 85
h j 106
h y 55
i q 122
i x 70
i z 110
j k 26
j m 112
j p 52
k r 7
l u 64
m s 53
n o 102
n p 103
n t 92
o bb 61
o p 23
p ba 42
p t 99
p u 68
p w 91
q x 65
q y 47
r s 28
r x 17
s u 45
s v 74
s x 51
s z 71
t bb 16
t u 90
t y 96
t z 120
u ba 35
v bb 57
w ba 4
z ba 31

Sample output:

T d q 1
T w ba 4
T k r 7
T a l 10
T f u 11
T c g 13
T d e 14
T t bb 16
T r x 17
T e r 20
T o p 23
T d v 24
T j k 26
T r s 28
T z ba 31
T b e 32
T u ba 35
T e g 37
T e u 40
T p ba 42
F s u 45
T q y 47
F b q 50
F s x 51
F j p 52
T m s 53
T h y 55
T v bb 57
T g i 59
F o bb 61
T l u 64
F q x 65
F p u 68
F c p 69
F i x 70
F s z 71
F c x 73
F s v 74
F b i 77
F c e 80
F a v 83
F g z 85
F f t 88
F t u 90
F p w 91
T n t 92
F f y 95
F t y 96
F p t 99
F n o 102
F n p 103
F h j 106
F g y 107
F i z 110
F j m 112
F d g 113
F e x 115
F c t 117
F t z 120
F i q 122

Sample input:_

a g 48
a l 46
a y 37
a z 27
b ba 23
b e 78
b g 33
b h 119
b v 18
b w 49
b y 115
c ba 97
c l 28
c q 16
c y 9
d e 12
d n 1
d w 6
e u 34
f ba 114
f l 71
f q 104
f t 84
f z 20
g k 110
g n 105
g s 38
g x 25
h i 87
h q 56
h s 58
h w 90
i l 60
i n 102
i o 45
j p 111
j x 41
k t 42
l m 83
l s 73
m bb 92
m v 74
n t 14
n z 53
o bb 89
o q 100
o w 51
o z 70
p s 64
p x 94
q ba 75
q v 93
q w 116
q z 72
r t 81
r y 30
s v 67
v y 107
v z 3
w bb 63

Sample output:

T d n 1
T v z 3
T d w 6
T c y 9
T d e 12
T n t 14
T c q 16
T b v 18
T f z 20
T b ba 23
T g x 25
T a z 27
T c l 28
T r y 30
T b g 33
T e u 34
T a y 37
T g s 38
T j x 41
T k t 42
T i o 45
F a l 46
F a g 48
T b w 49
T o w 51
F n z 53
T h q 56
F h s 58
F i l 60
T w bb 63
T p s 64
F s v 67
F o z 70
F f l 71
F q z 72
F l s 73
T m v 74
F q ba 75
F b e 78
F r t 81
F l m 83
F f t 84
F h i 87
F o bb 89
F h w 90
F m bb 92
F q v 93
F p x 94
F c ba 97
F o q 100
F i n 102
F f q 104
F g n 105
F v y 107
F g k 110
F j p 111
F f ba 114
F b y 115
F q w 116
F b h 119

Sample input:_

a h 21
a i 111
a o 1
a t 5
a x 77
b v 105
b w 47
b z 10
c h 2
c k 90
c v 74
c y 81
d m 19
d q 46
e j 24
e p 6
e r 107
e w 38
f o 33
f q 41
f s 80
g ba 18
g j 57
h m 64
h r 101
i k 83
i n 78
i t 40
j k 3
j n 51
j s 54
j u 28
k m 71
k o 106
k p 25
k r 48
k u 13
k w 70
k x 96
k z 50
l z 58
n p 31
n t 69
n v 91
n y 61
o ba 44
o q 109
o s 104
o t 95
o y 108
p ba 27
q v 114
q w 15
r ba 9
t u 66
t x 99
u w 93
v bb 35
y z 84
z bb 87

Sample output:

T a o 1
T c h 2
T j k 3
T a t 5
T e p 6
T r ba 9
T b z 10
T k u 13
T q w 15
T g ba 18
T d m 19
T a h 21
T e j 24
F k p 25
T p ba 27
F j u 28
T n p 31
T f o 33
T v bb 35
T e w 38
T i t 40
T f q 41
F o ba 44
T d q 46
T b w 47
F k r 48
F k z 50
F j n 51
T j s 54
F g j 57
T l z 58
T n y 61
F h m 64
F t u 66
F n t 69
F k w 70
F k m 71
T c v 74
T a x 77
F i n 78
F f s 80
F c y 81
F i k 83
F y z 84
F z bb 87
F c k 90
F n v 91
F u w 93
F o t 95
F k x 96
F t x 99
F h r 101
F o s 104
F b v 105
F k o 106
F e r 107
F o y 108
F o q 109
F a i 111
F q v 114

Ranking

Ruby _

Perl _

Python _

Io _

JavaScript _

Smalltalk _

J _

C _

D _

OCaml _

Haskell _

AWK _

sed _

Postscript _

GolfScript _

goruby _

Groovy _

Language Ranking_

return to the top page