CT49875

The Crystal bridges of Innkeeper

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Innkeeper runs the granary at the fjord village of Deepwater. Today the books show a list of bridges, and the numbers must be worked out before sundown. Task: Print YES if the directed graph contains a cycle, otherwise NO. Input format: First line: n and m. Next m lines: u v (directed). Output format: Print YES or NO. Constraints: 1 <= n <= 3888; 0 <= m <= 3888.

Example 1:

Input: 3410 583 2490 2354 625 804 1011 1472 437 2175 2349 1332 1174 771 3266 2514 2249 753 2554 2673 603 2034 2983 1534 1878 369 1496 2029 1748 1344 95 1388 3313 3332 1787 1225 3302 1516 258 1891 1659 249 890 779 1153 2451 2241 1277 1989 2630 1221 1404 3049 2073 110 2908 1589 2773 167 1766 184 2616 1415 27 361 2922 1814 647 2958 1332 2987 758 3130 976 2471 637 2498 1307 2431 2133 1884 2482 1959 1987 2336 680 3097 1317 1437 2095 1675 587 2108 563 599 955 822 113 112 857 112 461 1079 3207 1645 1474 408 2475 883 1090 1903 2501 2206 1508 207 882 3343 3244 171 367 1032 2318 202 22 3117 808 3404 410 1874 2364 1098 1231 1401 153 2887 39 772 1329 805 3298 694 2464 46 378 2710 263 3066 487 2495 3158 2102 1126 2730 41 139 2452 2098 1121 2855 1639 1781 757 2765 3062 289 3391 1652 409 1183 902 619 330 1632 2…
Output: NO

Example 2:

Input: 597 3121 281 556 67 449 147 132 520 536 379 472 267 135 382 167 112 399 418 595 340 312 45 174 185 207 206 211 289 51 95 192 253 272 355 462 442 449 506 463 169 504 45 232 322 102 588 266 369 382 189 52 375 474 333 166 256 138 208 269 39 291 356 533 595 518 377 210 298 1 370 264 36 398 415 26 299 319 463 95 427 61 477 353 273 554 140 137 440 527 300 169 294 577 502 97 163 587 103 195 149 45 74 561 124 137 216 106 482 331 567 353 386 339 326 494 51 385 412 254 521 22 101 290 76 464 311 305 119 83 547 425 456 148 253 321 469 61 510 332 272 505 44 317 231 327 107 363 54 308 271 518 354 379 571 549 88 150 316 438 594 398 29 188 320 558 347 127 271 297 65 518 107 246 596 79 236 11 149 267 232 375 532 245 228 414 555 167 235 563 552 193 366 339 57 258 554 539 5 354 519 39 184 501 180 112 62 494 …
Output: YES

Example 3:

Input: 1932 1822 1184 1308 591 911 1552 784 68 585 1785 1494 79 621 210 1232 1402 613 768 1074 24 39 195 703 83 1037 1419 1923 1247 1227 570 1159 1880 330 603 1863 894 1315 1599 304 1290 1589 1550 362 1454 1078 145 311 1031 1358 473 785 336 988 1222 399 1682 35 34 745 1417 1399 1415 867 883 1784 473 1198 1640 1297 1583 339 1910 1518 545 958 1711 1926 1015 952 1193 1103 1047 156 346 1690 1673 958 1894 590 1932 878 1879 1679 410 843 643 1307 229 682 507 923 1702 278 565 937 1382 763 42 433 285 1441 1408 1104 638 629 210 1171 81 1276 743 906 1119 1150 1589 1594 819 1176 329 761 246 744 868 828 1632 474 1552 1813 789 1489 1767 1481 985 1087 690 1163 687 173 1019 846 1629 1744 1179 1728 770 305 401 197 1721 1895 133 1133 588 1699 64 120 398 105 1689 149 701 1836 1352 1261 860 1409 1918 400 154 1621 85…
Output: NO

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Crystal bridges of Innkeeper - MEDIUM Coding Problem | CodeTikki