Minimum Spanning Tree

Submit

Your name:
File:
Open code-statistics:

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 _

RankUserSizeTimeDateStatistics
1shinh1140.13332008/03/17 09:50:440B / 51B / 57B
2ksk1150.55522008/03/29 14:12:220B / 27B / 80B
3flagitious1220.44662008/03/22 04:44:550B / 51B / 65B
4murky-satyr1130.15482008/07/30 07:34:370B / 51B / 57B

Perl _

RankUserSizeTimeDateStatistics
1tybalt89920.38162008/03/20 14:23:490B / ?B / ?B
2ais523(slightly cheat)1860.10592008/03/15 23:14:261B / ?B / ?B
3ais5231880.17312008/03/15 23:13:441B / ?B / ?B

Python _

RankUserSizeTimeDateStatistics
1recursive1680.10892009/01/22 03:14:550B / 101B / 48B

Io _

RankUserSizeTimeDateStatistics
1murky-satyr1783.00182008/07/30 08:49:500B / 117B / 49B

JavaScript _

RankUserSizeTimeDateStatistics
1nn1600.48452008/08/21 16:59:290B / 75B / 84B
2murky-satyr1610.48542008/08/21 01:15:010B / 74B / 86B

Smalltalk _

RankUserSizeTimeDateStatistics
1murky-satyr2510.80562008/07/21 00:57:270B / 154B / 80B

J _

RankUserSizeTimeDateStatistics
1I., S.1061.16662012/03/13 21:24:070B / 22B / 83B
2I., S.(shinh,recursive,et al.(set algebra))1060.22052012/03/22 06:34:120B / 33B / 73B
3I., S.(less slow)1080.17942012/03/13 21:30:530B / 23B / 84B

C _

RankUserSizeTimeDateStatistics
151b(embed)2070.07232008/03/21 02:53:147B / 94B / 102B
251b2440.10882008/03/21 02:47:550B / 113B / 127B
351b2090.14932009/09/23 20:49:240B / 93B / 113B

D _

RankUserSizeTimeDateStatistics
151b2330.04772009/09/23 21:15:530B / 122B / 103B

OCaml _

RankUserSizeTimeDateStatistics
1ksk2420.32942009/10/12 16:43:540B / 134B / 80B

Haskell _

RankUserSizeTimeDateStatistics
1notogawa(embed)2120.09542008/03/16 11:03:260B / ?B / ?B
2notogawa2130.18222008/03/16 10:56:030B / ?B / ?B
3fox2050.05752008/07/21 09:45:420B / 113B / 81B

AWK _

RankUserSizeTimeDateStatistics
1nn1260.10672008/07/20 14:14:380B / 61B / 61B

sed _

RankUserSizeTimeDateStatistics
1emoken15952.89932008/03/15 16:13:420B / 398B / 1026B

Postscript _

RankUserSizeTimeDateStatistics
1yshl(bin)1410.55972008/03/18 15:41:0254B / 53B / 31B
2yshl2550.58482008/03/18 15:40:500B / 181B / 37B

GolfScript _

RankUserSizeTimeDateStatistics
1irori781.65782008/03/25 22:37:520B / 10B / 66B

goruby _

RankUserSizeTimeDateStatistics
1murky-satyr880.10882010/01/04 16:49:510B / 30B / 54B
2leonid890.11102010/01/03 20:27:230B / 30B / 57B

Groovy _

RankUserSizeTimeDateStatistics
1murky-satyr1457.06282010/09/19 19:09:400B / 80B / 59B

Language Ranking_

RankLangUserSizeScore
1GolfScriptirori7810000
2gorubymurky-satyr888863
3Perltybalt89928478
4JI., S.1067358
5Rubymurky-satyr1136902
6AWKnn1266190
7Postscriptyshl(bin)1415531
8Groovymurky-satyr1455379
9JavaScriptnn1604875
10Pythonrecursive1684642
11Iomurky-satyr1784382
12Haskellfox2053804
13C51b(embed)2073768
14D51b2333347
15OCamlksk2423223
16Smalltalkmurky-satyr2513107
17sedemoken1595489

return top