CT50733

The bridges at Tangledeep

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the kelp forests of Tangledeep, Cyrus the reckoner keeps careful count of the bridges. Audit the season's records, every figure matters. 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 <= 3046; 0 <= m <= 3046.

Example 1:

Input: 3018 2293 827 2804 648 1543 1139 1233 862 2552 2044 2475 1330 2075 818 998 1712 2260 350 1436 2006 3006 359 1793 1539 1806 91 2777 422 2311 366 1067 1855 2610 1456 2985 438 1182 238 1286 1971 2225 337 2410 568 1146 13 1870 57 566 2340 2933 688 2317 1237 2730 771 2259 144 1816 98 2648 55 1862 1012 2822 525 2338 349 2028 1461 2134 2271 2807 1602 3009 360 1626 1074 2161 2515 2564 1229 1328 445 1655 1173 2812 1362 2408 2088 2614 640 747 744 822 611 1151 299 884 443 1588 218 2113 1068 1789 2224 2963 831 2348 1002 1198 251 1937 411 723 2524 2624 1060 1333 1427 2691 253 446 1716 2632 289 2179 1558 2822 807 840 1505 1742 10 2656 1467 1686 91 2420 2176 2291 2033 2147 1178 2843 579 2680 404 775 284 526 2175 2322 1558 2411 1731 1870 467 2023 755 1097 376 468 703 1707 1971 2345 813 2687 734 2759 845 1…
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: 6 15 4 5 1 5 3 4 5 6 3 5 2 6 1 4 1 6 3 6 4 6 2 4 1 2 2 3 2 5 1 3
Output: 1 2 3 4 5 6

Example 3:

Input: 554 2472 198 334 103 524 203 395 86 122 189 401 97 124 118 161 150 279 156 295 222 307 114 387 469 518 17 346 210 434 324 539 130 407 56 336 172 241 249 491 32 244 213 495 3 437 348 405 163 297 403 492 193 472 306 407 17 298 77 203 149 490 32 313 435 446 443 488 19 372 64 363 139 480 9 37 528 545 354 538 494 510 226 321 267 479 109 452 429 483 216 520 11 151 25 498 308 540 48 347 99 258 4 371 481 538 342 357 94 330 34 441 274 472 115 367 86 325 101 238 51 84 280 474 33 502 371 445 274 519 77 94 126 423 356 514 368 408 10 75 173 420 302 531 244 245 130 442 110 215 6 209 278 388 47 476 415 516 69 348 153 428 392 412 173 412 116 268 270 344 170 253 315 325 118 427 53 533 247 457 402 417 69 434 420 537 36 413 66 115 243 399 181 212 100 337 243 344 136 440 161 467 312 513 30 40 339 517 183 553 …
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 <= 3046; 0 <= m <= 3046.

Loading...
Test Cases:No test cases
No test cases available.
The bridges at Tangledeep - MEDIUM Coding Problem | CodeTikki