CT45650

The Build Order at Slitherwick

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the eel marshes of Slitherwick with crates of corridors, and Notary the cartographer must account for every last one. Task: Edges u -> v mean u must come before v. Print the lexicographically smallest valid ordering of the n jobs (space-separated), or IMPOSSIBLE if a cycle exists. Input format: First line: n and m. Next m lines: u v. Output format: Print the order or IMPOSSIBLE. Constraints: 1 <= n <= 2757; 0 <= m <= 2757.

Example 1:

Input: 623 1176 260 475 6 35 7 377 8 69 555 598 69 204 159 483 319 345 428 614 208 430 415 447 90 550 74 497 357 398 415 578 220 447 71 538 203 316 59 581 426 623 167 476 69 276 194 271 218 265 144 357 133 552 168 487 89 496 303 327 23 583 221 550 209 439 201 380 288 505 246 268 136 477 114 250 108 184 102 561 431 610 113 300 399 483 247 271 221 476 355 362 39 145 5 468 497 519 232 382 118 468 534 569 232 469 83 450 213 326 142 199 15 354 68 539 127 152 98 308 195 521 450 547 299 310 216 566 166 434 95 108 337 593 235 619 403 499 121 558 46 555 247 390 300 456 31 149 280 496 28 204 286 403 105 568 399 612 97 370 113 295 19 88 88 381 15 377 30 495 14 482 229 481 413 578 367 424 5 143 187 504 76 378 74 355 235 260 311 453 361 378 125 552 71 330 308 423 92 609 127 232 12 507 223 243 33 140 300 387 4…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 2:

Input: 1710 671 742 987 1009 1242 601 1300 189 1695 662 1369 284 1689 1029 1352 356 1129 27 1690 672 1681 190 297 112 140 668 1019 121 1461 30 51 191 479 1546 1569 608 1364 254 425 389 911 241 1023 701 766 38 437 112 852 515 1330 393 973 660 1606 888 971 589 1574 1118 1656 168 1046 223 444 24 276 140 465 244 1162 43 1101 546 726 496 598 373 1707 405 1077 103 410 234 386 70 827 248 997 222 1426 88 1216 190 1589 569 1187 1266 1455 343 1163 469 672 607 1291 1146 1614 215 1350 167 736 514 1387 397 719 272 996 470 1184 227 504 253 667 477 1255 639 1304 606 1404 813 1126 36 732 1289 1618 393 1390 333 481 1338 1431 84 587 138 1309 249 1244 304 396 1123 1315 353 634 393 1238 1259 1471 567 803 1108 1202 681 1405 119 392 277 1610 535 1484 270 1639 183 968 247 865 288 1346 478 1113 762 1416 107 1578 979 149…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 3:

Input: 1872 160 169 400 132 732 1096 1161 250 1619 1040 1488 766 1567 409 1433 376 529 401 1851 1480 1503 1399 1443 1287 1599 239 1851 188 1836 1492 1617 446 987 639 762 1444 1645 792 1556 470 720 284 1446 544 981 1241 1364 469 1045 732 1036 60 1332 1160 1354 137 448 76 943 701 1736 560 1804 440 1107 239 325 942 1220 134 217 92 236 938 1451 933 1327 722 1553 572 629 995 1759 223 1657 477 1604 239 1734 693 1834 780 1564 1269 1614 11 24 1390 1629 162 1867 500 1673 335 639 135 402 537 1233 1198 1724 257 1597 19 281 183 604 816 1523 779 1250 78 1647 945 1737 795 1266 240 359 203 507 903 1656 261 1725 17 1570 1451 1480 3 1728 517 1493 202 515 933 1790 1111 1701 324 325 269 1871 1343 1454 915 1831 848 1271 872 1703 626 1648 1772 1847 93 945 259 495 624 1001 39 429 17 1268 1170 1619 441 1589 168 1323 69…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Constraints:

1 <= n <= 2757; 0 <= m <= 2757.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order at Slitherwick - MEDIUM Coding Problem | CodeTikki