CT56504

The roads at Goldmeadow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Wamika inherited the gallery at the trading post of Goldmeadow along with its curious bookkeeping system for roads. Time to make sense of it. 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 <= 2244; 0 <= m <= 2244.

Example 1:

Input: 1815 1343 1041 68 1289 1087 1192 303 201 452 366 1673 669 237 1421 1438 724 835 28 577 1177 54 659 200 1745 1011 1592 1323 1379 492 1315 651 1035 1255 938 640 808 1798 770 937 1715 388 994 992 1269 1247 1028 898 172 930 1251 1466 1365 1330 1709 1129 1503 1718 686 606 1725 1571 460 279 407 1549 1754 991 1427 271 57 752 1715 1055 1425 641 256 745 940 1206 1124 1150 771 238 1766 145 260 535 1722 1620 1205 357 419 793 784 1687 1223 212 1510 1060 822 495 1196 1136 1464 1024 1720 1312 1706 910 1588 1251 1706 172 1427 769 1145 976 783 968 860 1200 1310 989 971 375 200 314 903 519 251 455 1609 1656 1587 912 802 1685 460 301 780 1647 76 874 1186 287 1057 29 88 743 339 1566 1212 803 891 1138 1582 76 1474 1383 631 138 680 34 136 1595 1245 1607 103 1090 1138 573 20 144 382 477 1560 1750 398 1577 1579 …
Output: NO

Example 2:

Input: 1890 2231 714 1745 1220 486 922 261 1743 930 1611 324 661 1086 160 524 1467 395 1557 816 722 1233 857 1885 1353 1211 1628 1623 1390 653 1026 1826 1386 1622 1774 147 1517 74 879 611 626 618 409 814 1286 94 1088 1012 1878 1808 1618 1255 1645 1303 1880 156 1605 1699 319 1614 431 585 1451 489 1504 84 1319 1436 1127 51 350 1393 382 1313 1789 1233 710 765 18 858 1753 1694 111 1066 1791 1269 1128 515 273 1414 1026 1032 1724 1486 89 1429 1346 1781 1803 906 1889 1311 275 80 296 1846 828 347 1219 47 1807 1718 1034 443 99 263 5 719 150 519 21 632 1062 607 111 246 1471 1400 1310 1224 1822 1258 748 52 1472 473 1559 232 42 196 234 520 1663 196 817 226 1609 1844 1249 1105 1431 417 720 651 1334 1508 765 472 538 685 1759 929 517 735 971 177 1519 25 1807 839 504 615 1585 2 347 1886 1254 175 1293 1713 988 18…
Output: YES

Example 3:

Input: 298 1188 247 206 33 28 186 55 260 218 130 61 257 24 213 45 4 262 177 77 235 50 275 35 29 257 33 66 25 87 165 41 114 37 291 253 297 291 121 180 160 221 139 26 5 124 242 204 181 10 281 240 8 238 208 146 255 37 206 243 185 97 166 170 185 216 238 286 98 69 42 8 30 190 192 5 56 128 97 12 12 274 85 283 294 50 182 162 280 6 224 75 233 294 265 177 79 105 202 88 83 281 229 111 199 183 92 138 93 254 107 259 51 81 69 81 95 135 182 88 150 251 140 184 108 266 43 98 214 33 220 94 294 268 161 252 31 54 228 223 106 45 32 277 51 133 133 76 257 92 186 82 24 59 61 85 128 137 29 78 78 203 166 208 187 70 148 134 198 1 173 27 270 22 243 85 155 133 236 6 173 266 45 30 157 142 169 74 30 198 66 103 82 50 37 160 81 156 240 57 32 36 269 262 42 253 70 90 235 33 14 249 88 80 295 135 273 196 57 33 7 286 110 258 53 249 …
Output: YES

Constraints:

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

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