Topological Sorting

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

Sort items according to their partial ordering.

[Input]
A list of item descriptions is given. One line corresponds to one item. Every item is assigned integer ID.
In a description of an item, the ID of the item is followed by colon, and its precedents.
For example,
1: 2 4 5
means that item 2, 4, 5 must precede item 1.
Every item has its description.

[Output]
Print sorted list of items.
If there are multiple solutions, print lexicographically first one.

Options

exec is denied

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

Sample input:_

1:
2: 1 4
3: 1
4:
5: 2 3

Sample output:

1
3
4
2
5

Sample input:_

1: 4
2:
3: 5
4: 3 6
5:
6:
7: 2
8: 3 4 9
9: 3

Sample output:

2
5
3
6
4
1
7
9
8

Sample input:_

1: 65 66
2: 96
3: 36
4: 37
5: 1 47 61
6: 25 26
7: 5
8: 31 62
9: 2 4 56
10: 4 6 54
11: 30 67 68
12: 24 34 78
13: 88
14: 57
15: 53 76 98
16: 11 12 60 69
17: 32 44
18: 25 38
19: 53 60 76
20: 24 27 93
21: 22 28
22: 23 63
23: 71 78 79
24: 28 49
25: 47
26: 53 61 67
27: 52
28: 66
29: 92
30: 33 50 72
31: 64
32: 13
33: 20 58
34: 8 42 51 75
35: 19 67
36: 22 25 48
37: 24 97
38: 2 25 55 99
39: 62 92 96
40: 88 97
41:
42: 9 17 38
43:
44:
45: 10 35 82
46: 4 83
47: 28
48: 79 83
49:
50:
51: 29 58
52: 1 44
53: 24 25 27 41 85
54: 31
55: 30 46 72
56: 40
57: 2 53 54 86
58: 32 67
59: 53
60: 27
61:
62: 82
63: 16 23 62
64: 60
65: 24 29 72 95
66: 92
67: 54 91
68: 13
69: 34 50
70: 3 35 77
71: 26 34 86
72: 28
73: 13 30
74: 20
75: 66
76: 9 10 14 30 84
77: 39 62
78: 73
79: 9 43
80: 12 55
81: 4 55
82: 44 74 91
83: 67 97
84: 24 69
85: 4 16 24 32
86: 9
87: 85
88: 65 74
89: 23 92
90: 7 47
91: 24 41 90
92:
93: 43 52
94: 4 44
95:
96: 64 94
97: 20 78 82
98: 3 22 45
99: 9 20 77 82

Sample output:

41
43
44
49
50
61
92
29
66
28
24
47
25
72
75
95
65
1
5
7
52
27
60
64
31
54
90
91
67
93
20
74
82
62
8
88
13
32
17
58
33
30
51
68
11
73
78
97
37
4
40
56
83
46
55
81
94
96
2
9
39
77
79
48
86
99
38
18
42
34
12
69
16
80
84
85
53
26
6
10
57
14
59
71
23
63
22
21
36
3
76
19
35
45
70
87
89
98
15

Ranking

Ruby _

RankUserSizeTimeDateStatistics
1flagitious480.14132008/03/28 01:10:120B / 23B / 22B
2shinh490.12142008/03/24 02:11:380B / 21B / 25B
3niha560.25852008/03/24 01:30:140B / 25B / 28B
4murky-satyr470.29882008/03/30 00:43:540B / 22B / 22B

Perl _

RankUserSizeTimeDateStatistics
1tybalt89460.06802008/03/24 01:19:260B / ?B / ?B
2shinh470.06742008/03/24 02:29:570B / 22B / 22B
3Terje K470.06582008/03/26 18:05:020B / 23B / 19B

Python _

RankUserSizeTimeDateStatistics
1kt3k1490.21412008/03/24 01:00:210B / 98B / 35B
2recursive1430.23452009/01/11 05:17:120B / 85B / 41B

PHP _

RankUserSizeTimeDateStatistics
1o-cn1020.08352009/12/06 20:55:060B / 47B / 52B
2daira2270.43742008/04/23 13:19:451B / 111B / 111B

Scheme _

RankUserSizeTimeDateStatistics
1kaki(murky-satyr)1280.12122012/12/05 07:12:250B / 66B / 58B
2murky-satyr1460.42722008/06/27 21:14:090B / 82B / 59B

Io _

RankUserSizeTimeDateStatistics
1murky-satyr1613.43982008/03/27 03:58:270B / 111B / 41B

JavaScript _

RankUserSizeTimeDateStatistics
1murky-satyr1090.15612008/03/29 00:46:400B / 47B / 60B
2REM3700.09742008/03/26 13:09:300B / ?B / ?B
3murky-satyr1020.16222008/05/23 10:49:300B / 37B / 64B

Lua _

RankUserSizeTimeDateStatistics
1murky-satyr1250.10562008/06/03 10:43:120B / 62B / 57B

Tcl _

RankUserSizeTimeDateStatistics
1murky-satyr1000.24312008/07/11 07:13:360B / 50B / 32B

Smalltalk _

RankUserSizeTimeDateStatistics
1murky-satyr2180.54412008/03/28 00:30:460B / 143B / 57B
2murky-satyr1060.70662008/06/27 02:08:440B / 63B / 40B

J _

RankUserSizeTimeDateStatistics
1I., S.610.11852011/08/11 23:54:450B / 17B / 44B

C _

RankUserSizeTimeDateStatistics
151b1760.07902008/03/24 19:58:350B / 84B / 92B

Haskell _

RankUserSizeTimeDateStatistics
1fox1360.16712008/07/13 15:44:350B / 70B / 60B

AWK _

RankUserSizeTimeDateStatistics
1nn1180.10302008/10/05 11:52:000B / 46B / 66B

Postscript _

RankUserSizeTimeDateStatistics
1yshl(bin)1230.52892008/03/25 21:58:1459B / 36B / 28B
2yshl2320.59112008/03/25 21:58:010B / 172B / 27B

GolfScript _

RankUserSizeTimeDateStatistics
1flagitious331.15772008/03/28 10:27:260B / 4B / 29B
2irori351.09122008/03/24 01:51:420B / 3B / 32B

goruby _

RankUserSizeTimeDateStatistics
1murky-satyr450.32192008/07/26 02:21:340B / 16B / 26B

Groovy _

RankUserSizeTimeDateStatistics
1murky-satyr869.37952008/03/29 02:48:440B / 46B / 36B
2nn1199.83922008/03/29 15:06:000B / 78B / 33B
3murky-satyr823.58822009/12/02 02:07:220B / 44B / 36B
4nn11610.11692008/03/29 19:44:120B / 73B / 39B

Language Ranking_

RankLangUserSizeScore
1GolfScriptflagitious3310000
2gorubymurky-satyr457333
3Perltybalt89467173
4Rubymurky-satyr477021
5JI., S.615409
6Groovymurky-satyr824024
7Tclmurky-satyr1003300
8JavaScriptmurky-satyr1023235
9PHPo-cn1023235
10Smalltalkmurky-satyr1063113
11AWKnn1182796
12Postscriptyshl(bin)1232682
13Luamurky-satyr1252640
14Schemekaki(murky-satyr)1282578
15Haskellfox1362426
16Pythonrecursive1432307
17Iomurky-satyr1612049
18C51b1761875

return top