|
0 / 0 / 0
Регистрация: 18.06.2020
Сообщений: 17
|
|
Система непересекающихся множеств20.06.2020, 09:30. Показов 7758. Ответов 20
Метки нет (Все метки)
Условие: Напишите программу, которая будет содержать реализацию структуры данных для системы непересекающихся множеств и обрабатывать запросы следующих видов. «RESET n» — создать систему непересекающихся множеств на элементах от 0 до n−1, причём первое множество будет состоять из одного элемента 0, второе множество — из элемента 1, третье — из элемента 2, ..., последнее — из элемента n−1. Если до этого структура данных уже содержала некоторый набор множеств, то вся информация о них утрачивается. При этом следует вывести два слова через пробел — «RESET DONE». «JOIN a b» — объединить множества, которым принадлежат элементы a и b. Если элементы и так принадлежали одному множеству, то требуется вывести «ALREADY a b», если же действие можно успешно выполнить, то ничего выводить не следует. «CHECK a b» — проверить, одному ли множеству принадлежат элементы a и b, и, если одному, то вывести «YES», а иначе — «NO». Формат входных данных: Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату. Гарантировано, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 250000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n−1, где n — параметр последнего выполненного запроса RESET. Формат выходных данных: Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному множеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке). входные данные: RESET 15 JOIN 14 10 JOIN 13 8 JOIN 0 9 JOIN 8 3 JOIN 4 1 JOIN 10 5 JOIN 8 4 CHECK 2 11 JOIN 4 1 JOIN 2 6 CHECK 9 1 JOIN 6 5 CHECK 10 5 выходные данные: RESET DONE NO ALREADY 4 1 NO YES
0
|
|
( Лучшие ответы (1)
| 20.06.2020, 09:30 | |
|
Ответы с готовыми решениями:
20
Найти подсемейство попарно непересекающихся множеств Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств Поиск непересекающихся множеств |
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
|
| 20.06.2020, 15:42 | |
|
У вас есть название структуры, в чем проблема?
https://e-maxx.ru/algo/dsu
0
|
|
|
0 / 0 / 0
Регистрация: 18.06.2020
Сообщений: 17
|
|
| 20.06.2020, 15:48 [ТС] | |
|
я понимаю алгоритм но не получается написать его на с++. Буду очень благодарен если поможете написать
0
|
|
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
|||||||||||
| 20.06.2020, 18:53 | |||||||||||
А работать с этим вот так
0
|
|||||||||||
|
0 / 0 / 0
Регистрация: 18.06.2020
Сообщений: 17
|
|
| 20.06.2020, 23:23 [ТС] | |
|
можешь пж готовым кодом показать, чтоб мне понятней было
0
|
|
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
||||||
| 21.06.2020, 12:15 | ||||||
 Сообщение было отмечено иВаН0301 как решение
Решение
иВаН0301,
1
|
||||||
|
0 / 0 / 0
Регистрация: 18.06.2020
Сообщений: 17
|
|
| 21.06.2020, 14:38 [ТС] | |
|
Если вбить такие данные то программа выдает неверный ответ. Как это исправить?
RESET 12345 JOIN 6824 6334 CHECK 5705 12119 CHECK 9961 4482 JOIN 4827 11942 CHECK 3902 2259 JOIN 5076 37 CHECK 5447 7550 CHECK 1869 11538 CHECK 9894 4690 CHECK 4664 5328 CHECK 7692 6868 CHECK 778 9741 CHECK 1842 9845 JOIN 8942 9040 CHECK 3545 11460 CHECK 2661 3005 CHECK 7284 3548 CHECK 6411 7609 CHECK 1586 7376 CHECK 11323 12281 CHECK 2082 3773 CHECK 4639 4833 CHECK 1632 9930 CHECK 5021 10041 CHECK 6270 6727 CHECK 5097 3228 CHECK 9161 945 CHECK 3229 11310 CHECK 4596 1150 CHECK 5662 3430 CHECK 10383 12287 CHECK 11876 9758 CHECK 4068 685 CHECK 1655 6417 CHECK 9203 8192 CHECK 3602 4041 CHECK 11020 9374 CHECK 7323 10854 CHECK 53 4734 CHECK 3788 6900 CHECK 2548 3728 CHECK 2421 5462 CHECK 9514 10468 CHECK 5106 6590 CHECK 10453 4174 CHECK 5844 11008 CHECK 8140 3195 CHECK 9503 1587 CHECK 6618 1113 CHECK 2936 2453 CHECK 11277 8127 CHECK 11834 6038 CHECK 6191 7958 CHECK 11511 6811 CHECK 7710 11927 CHECK 6530 4886 CHECK 11499 7797 CHECK 6306 10322 CHECK 12044 3557 CHECK 2510 2600 CHECK 2343 5516 CHECK 4078 2910 CHECK 10285 11837 CHECK 9832 11412 CHECK 4844 2154 CHECK 9080 2368 CHECK 7441 4204 CHECK 9373 5715 CHECK 3934 78 CHECK 10204 184 CHECK 193 604 CHECK 3760 8071 CHECK 5769 110 CHECK 5786 8326 CHECK 7708 12010 JOIN 8600 1832 CHECK 11301 7213 CHECK 10851 4144 CHECK 5535 2161 CHECK 12044 10466 CHECK 7679 4908 CHECK 8304 4745 CHECK 2168 4474 CHECK 5613 9905 CHECK 4414 3625 CHECK 7814 12027 CHECK 7518 7487 CHECK 2668 1763 CHECK 8480 3102 CHECK 4099 4802 CHECK 1924 1543 CHECK 1836 716 CHECK 10380 5160 CHECK 4877 142 CHECK 6842 7900 CHECK 235 1925 CHECK 4667 6551 CHECK 1349 140 CHECK 9349 2125 CHECK 10121 5026 CHECK 1018 11506 CHECK 2800 10807 CHECK 9010 1926 CHECK 9576 7970 CHECK 7164 10413 CHECK 3487 4741 CHECK 5629 2625 CHECK 2617 6902 JOIN 916 3737 CHECK 8260 1264 CHECK 7981 5030 CHECK 8808 6411 CHECK 9418 2579 CHECK 1484 6317 CHECK 5233 6613 CHECK 1200 11477 CHECK 415 2303 CHECK 5108 6477 CHECK 10505 7456 CHECK 7060 648 CHECK 6072 490 CHECK 8211 2140 CHECK 8526 9357 CHECK 11524 10926 CHECK 10112 677 CHECK 11696 11585 CHECK 4565 11884 CHECK 12053 9951 CHECK 4627 6654 CHECK 2963 10187 CHECK 11635 911 CHECK 593 4675 CHECK 6511 11409 CHECK 5480 9114 CHECK 2860 1626 CHECK 9934 5053 CHECK 1637 389 CHECK 10176 1993 CHECK 3536 10548 JOIN 7510 4296 CHECK 8079 11462 CHECK 328 6098 CHECK 7727 875 CHECK 2587 1017 CHECK 11486 824 CHECK 7152 6745 CHECK 7008 2800 CHECK 11258 9699 JOIN 7605 11192 CHECK 11430 3829 CHECK 5204 5997 CHECK 8256 6467 CHECK 8213 8683 CHECK 11047 5601 CHECK 10075 4084 CHECK 11502 6287 CHECK 10318 8876 CHECK 9826 9010 CHECK 7619 12164 CHECK 9232 6704 JOIN 1539 4975 JOIN 11247 8753 CHECK 5519 2971 CHECK 5201 9200 CHECK 8519 2917 CHECK 2865 3599 CHECK 8787 9601 CHECK 2078 4758 CHECK 5565 1670 JOIN 2943 2088 CHECK 4681 5049 CHECK 8876 608 CHECK 1801 8543 JOIN 9085 498 CHECK 8438 4536 CHECK 7038 2840 CHECK 3403 11224 CHECK 2610 4944 CHECK 8010 8680 CHECK 6239 9496 CHECK 8075 10997 CHECK 8081 9603 CHECK 6705 12084 CHECK 4220 7030 CHECK 8256 5994 CHECK 1355 8137 CHECK 5496 5885 CHECK 7345 4186 CHECK 10893 9289 CHECK 1663 1107 CHECK 3958 5454 CHECK 148 1911 CHECK 11683 4213 CHECK 4513 8973 CHECK 11903 2919 CHECK 3561 2557 CHECK 1308 1282 CHECK 6923 5402 CHECK 7914 3878 CHECK 9600 11626 CHECK 6698 47 CHECK 6692 5938 CHECK 163 6234 CHECK 1515 6493 CHECK 2355 58 CHECK 3870 2772 CHECK 3039 5985 CHECK 3740 1954 CHECK 6541 8380 CHECK 10728 4765 JOIN 10008 5787 CHECK 9018 1723 JOIN 5071 7200 CHECK 11333 1071 CHECK 8480 1950 CHECK 3309 2598 CHECK 12249 10116 CHECK 8405 7864 CHECK 7619 7516 CHECK 11662 6021 CHECK 5557 8070 CHECK 4806 11596 CHECK 11962 5602 CHECK 11769 8791 CHECK 12290 11211 CHECK 2363 1054 JOIN 5131 1367 CHECK 6995 7958 JOIN 5893 7479 CHECK 5314 10866 CHECK 7462 8851 CHECK 1146 12022 CHECK 10647 3925 CHECK 2255 4098 CHECK 8103 6007 CHECK 8762 4575 CHECK 7552 6052 CHECK 4449 11885 CHECK 12175 229 CHECK 1655 2802 CHECK 4053 10016 CHECK 7224 8843 CHECK 12170 2730 CHECK 8183 3270 CHECK 9464 905 CHECK 204 1816 CHECK 10580 1988 CHECK 5992 3991 CHECK 7604 7636 CHECK 10004 992 CHECK 6936 9970 CHECK 8194 6028 CHECK 6249 7572 CHECK 943 6474 CHECK 8419 7944 CHECK 3871 7585 CHECK 11064 2609 CHECK 1164 3729 CHECK 3244 9573 CHECK 7081 5623 CHECK 11207 8779 CHECK 5764 3150 JOIN 4460 2557 JOIN 9789 9232 CHECK 3998 7950 JOIN 11672 1012 CHECK 9762 5912 CHECK 1908 4415 CHECK 4319 5204 JOIN 6355 8166 CHECK 3447 9442 CHECK 378 2376 CHECK 9220 2431 CHECK 7145 11511 CHECK 7332 6486 CHECK 3332 7534 CHECK 7783 9646 CHECK 10697 3526 CHECK 11408 11027 CHECK 11892 7185 CHECK 8850 10156 CHECK 11192 11305 CHECK 7922 681 CHECK 8627 6289 CHECK 1532 5177 CHECK 1381 2019 CHECK 8023 2237 CHECK 2327 7824 CHECK 7926 11058 CHECK 2258 5651 CHECK 2742 8941 CHECK 6089 7128 CHECK 2522 3503 CHECK 9257 1881 CHECK 2661 6253 CHECK 7933 8462 CHECK 7586 6365 CHECK 985 8360 CHECK 11495 88 CHECK 11599 7465 CHECK 11369 7328 CHECK 9252 6608 CHECK 7208 9535 CHECK 9670 10898 CHECK 7467 3755 CHECK 12129 7506 CHECK 9990 7509 CHECK 10233 5435 CHECK 1142 3340 JOIN 5538 8483 CHECK 3489 1560 CHECK 6184 2785 CHECK 865 1047 CHECK 73 9277 CHECK 1481 9152 CHECK 1233 6582 CHECK 3449 159 CHECK 10208 10380 CHECK 1851 3025 CHECK 6674 266 CHECK 4338 545 CHECK 4954 2741 CHECK 3115 10396 CHECK 7791 2599 CHECK 7240 2042 CHECK 241 8670 CHECK 12105 3523 CHECK 9916 7296 CHECK 405 1234 CHECK 2995 11736 CHECK 11784 8554 CHECK 6172 1263 CHECK 10168 7514 CHECK 8922 5973 CHECK 2144 10986 CHECK 5874 2284 CHECK 8146 10567 CHECK 8295 9815 CHECK 9487 8551 CHECK 10838 4610 CHECK 3065 3752 CHECK 233 9261 CHECK 4611 1795 CHECK 1144 170 CHECK 1520 3333 CHECK 4022 8896 CHECK 7231 5296 CHECK 6321 6479 CHECK 11863 7102 CHECK 3455 8486 CHECK 11777 4860 CHECK 10086 10861 CHECK 9761 1852 CHECK 12110 4951 CHECK 9135 5973 CHECK 9253 12074 CHECK 8153 1643 CHECK 6450 7581 CHECK 8510 1854 CHECK 10900 10573 CHECK 12008 1550 CHECK 5765 2699 CHECK 2529 7172 CHECK 4381 1131 CHECK 8805 4326 CHECK 9320 3989 CHECK 11293 9658 CHECK 2206 4603 CHECK 4352 3396 CHECK 2443 3184 CHECK 9272 11969 CHECK 9168 3684 CHECK 12045 12097 CHECK 6854 2141 CHECK 3468 5926 CHECK 3580 318 CHECK 1099 8387 CHECK 5482 4360 CHECK 10268 7152 CHECK 5259 337 CHECK 7068 7768 CHECK 9043 5192 CHECK 748 3181 CHECK 8148 10761 CHECK 3320 5137 CHECK 6750 2739 CHECK 9436 3964 CHECK 3343 3656 CHECK 2523 3735 CHECK 3251 8623 CHECK 588 4695 CHECK 2095 12259 CHECK 8976 7720 CHECK 1214 4071 CHECK 7905 5487 CHECK 10540 9217 CHECK 10797 1836 CHECK 5340 10080 CHECK 8546 7740 CHECK 8880 6752 CHECK 707 11055 CHECK 11243 4141 CHECK 3880 7051 JOIN 11455 5791 CHECK 21 742 CHECK 11372 9248 CHECK 3335 945 CHECK 5303 9550 CHECK 6316 11854 CHECK 11688 8753 CHECK 7738 7042 CHECK 7229 12244 CHECK 2660 4769 CHECK 11981 9142 CHECK 7679 6540 CHECK 7838 5600 CHECK 5006 4978 CHECK 2088 11142 CHECK 2445 3648 CHECK 6760 11001 CHECK 3134 2669 CHECK 3545 653 CHECK 2499 8838 CHECK 2378 8683 CHECK 11197 11882 CHECK 10018 8018 CHECK 11100 5076 CHECK 2677 4396 CHECK 8055 10670 CHECK 7537 2934 CHECK 11900 3822 CHECK 10809 9945 CHECK 7733 9880 CHECK 8249 2330 CHECK 6460 4987 CHECK 9618 8144 CHECK 10879 9285 CHECK 10293 12129 CHECK 8184 9561 CHECK 6741 1774 CHECK 12279 434 CHECK 11773 11780 CHECK 10737 8232 CHECK 3715 10450 CHECK 2136 3432 CHECK 8839 5907 CHECK 3351 8131 CHECK 10727 10629 CHECK 3239 3442 CHECK 10681 4718 CHECK 6134 11831 CHECK 8738 1653 CHECK 3377 3481 CHECK 12054 236 CHECK 1898 1023 CHECK 8157 8707 CHECK 3546 8346 CHECK 10471 11400 CHECK 7065 8935 CHECK 2663 1529 CHECK 4015 10221 CHECK 9467 7811 CHECK 10542 844 CHECK 4881 9099 CHECK 1570 8706 CHECK 9405 8456 CHECK 10556 7975 CHECK 3388 8044 CHECK 6272 12319 CHECK 1775 10133 CHECK 5609 5955 CHECK 893 2257 CHECK 4888 4750 CHECK 6645 7266 CHECK 6702 10913 CHECK 6645 479 CHECK 4550 4422 CHECK 4397 16 CHECK 7833 10843 CHECK 1847 11596 CHECK 2619 4380 CHECK 9462 7728 CHECK 5154 11069 CHECK 3730 6804 CHECK 1773 704 CHECK 6125 7207 CHECK 5869 7511 CHECK 698 7103 CHECK 9850 1563 CHECK 9492 9566 CHECK 6833 3132 CHECK 4512 10003 CHECK 7075 6557 CHECK 341 9273 CHECK 1353 1892 CHECK 10389 65 CHECK 2003 3736 CHECK 2244 6286 CHECK 7519 6827 CHECK 6459 6145 CHECK 10285 11548 CHECK 8290 5116 CHECK 6078 8652 CHECK 5566 6640 CHECK 5900 10314 CHECK 4495 7256 CHECK 8421 5713 JOIN 4287 3271 CHECK 10700 2138 JOIN 205 12118 CHECK 11622 12114 CHECK 10481 590 CHECK 6816 6148 CHECK 8193 7670 CHECK 4415 4026 CHECK 726 3088 CHECK 10393 414 CHECK 3848 6447 CHECK 3690 4758 CHECK 7498 12323 JOIN 11647 3879 CHECK 12254 669 CHECK 5809 1731 CHECK 11622 9385 CHECK 6339 4359 CHECK 1585 10048 CHECK 5427 3745 CHECK 4129 10599 CHECK 5244 5158 CHECK 11447 5544 JOIN 5630 9364 JOIN 6840 2503 CHECK 8764 5306 CHECK 11045 8740 CHECK 11381 4755 CHECK 3565 11932 CHECK 6646 2083 CHECK 8920 10883 CHECK 5821 8433 CHECK 10330 582 CHECK 2737 8656 CHECK 8011 7590 JOIN 4937 10935 CHECK 4712 1228 CHECK 7162 9905 CHECK 10946 7194 CHECK 839 11770 CHECK 3394 2645 CHECK 675 1927 CHECK 2480 1428 CHECK 6858 3542 CHECK 1401 7789 CHECK 8391 7824 CHECK 6376 8793 CHECK 9230 1677 CHECK 3657 7961 CHECK 11671 684 CHECK 8939 1648 CHECK 7058 821 CHECK 119 10677 CHECK 1623 8891 CHECK 841 5584 CHECK 2612 191 CHECK 5093 1107 CHECK 5227 103 CHECK 12274 10324 CHECK 12170 2693 CHECK 11909 5084 CHECK 1848 10679 CHECK 5767 3420 CHECK 704 1439 CHECK 621 10891 CHECK 5653 8197 CHECK 10252 3276 CHECK 582 5763 CHECK 9102 6366 CHECK 1973 10819 CHECK 2556 3994 CHECK 1442 9133 CHECK 2554 10827 CHECK 1297 4453 CHECK 7056 1601 CHECK 7416 5363 CHECK 10142 2459 CHECK 4343 9816 CHECK 718 113 CHECK 656 8070 CHECK 3906 11959 CHECK 8007 5507 CHECK 2144 10756 CHECK 4668 1790 CHECK 7093 8715 CHECK 7373 1198 CHECK 9183 2930 JOIN 4762 5469 CHECK 10225 5608 CHECK 10149 11062 CHECK 1917 8038 CHECK 4360 5693 CHECK 11514 8309 CHECK 6766 489 CHECK 8321 7470 CHECK 5208 8160 CHECK 4629 1259 JOIN 11 9700 CHECK 11833 3154 CHECK 8922 6738 CHECK 3975 11969 CHECK 11871 4124 CHECK 1448 3118 CHECK 4281 10698 CHECK 1826 8275 CHECK 6521 6809 CHECK 655 11430 CHECK 6379 7551 CHECK 361 3789 CHECK 2799 11434 CHECK 601 2159 CHECK 1430 12157 CHECK 4346 4074 CHECK 5246 3947 CHECK 4646 6461 CHECK 4946 5024 CHECK 2317 11772 CHECK 5936 1441 CHECK 5636 1628 CHECK 1883 6816 CHECK 4812 5230 CHECK 1866 8310 CHECK 6238 3477 CHECK 1405 4592 JOIN 10395 8235 CHECK 1032 11975 CHECK 4489 9259 CHECK 6373 8388 CHECK 2264 5927 CHECK 6300 10371 CHECK 8485 11458 CHECK 11927 2509 CHECK 146 12054 CHECK 10559 10428 CHECK 4021 10343 CHECK 10515 2270 CHECK 6878 9817 CHECK 6538 7887 CHECK 10450 5195 CHECK 12212 1164 CHECK 12258 5790 CHECK 4121 9348 CHECK 592 11094 CHECK 9551 6097 CHECK 8947 11147 CHECK 9365 613 CHECK 6495 5809 CHECK 6292 6120 CHECK 849 182 CHECK 6568 7011 CHECK 2036 5417 CHECK 9423 1048 CHECK 4235 7954 JOIN 2782 1862 CHECK 10142 2340 CHECK 9131 6558 CHECK 5831 4085 CHECK 5577 3278 CHECK 11754 3866 CHECK 8976 3293 CHECK 10555 10443 CHECK 9375 7452 CHECK 5695 8934 CHECK 1539 1903 CHECK 7262 10312 CHECK 12119 11642 CHECK 5450 7825 CHECK 11754 948 CHECK 6705 75 CHECK 7456 11738 CHECK 3380 441 CHECK 1363 3659 CHECK 8613 1088 CHECK 7679 666 CHECK 10770 3402 CHECK 11153 2872 CHECK 10563 4508 CHECK 3202 7665 CHECK 5678 8965 CHECK 11339 7908 CHECK 833 9495 CHECK 11649 10968 CHECK 5936 348 CHECK 8982 10872 CHECK 5515 10635 CHECK 8343 7137 CHECK 7603 3995 CHECK 2167 7879 CHECK 10889 1816 CHECK 5191 5906 CHECK 6748 5224 CHECK 8867 3582 CHECK 4244 11146 CHECK 6414 10505 CHECK 6300 2403 CHECK 9250 8798 CHECK 698 8661 CHECK 12273 9967 CHECK 8741 8339 CHECK 3935 566 CHECK 3873 990 CHECK 127 3454 CHECK 5646 4641 CHECK 5584 4479 CHECK 7993 249 CHECK 10041 4640 CHECK 10655 4860 CHECK 7717 5117 CHECK 10639 5548 CHECK 7633 11683 CHECK 10654 10547 CHECK 9001 12036 JOIN 10238 3904 CHECK 5299 4060 CHECK 3751 1267 CHECK 5717 5821 CHECK 1421 3187 CHECK 3328 1201 CHECK 3951 1768 CHECK 9625 8899 CHECK 10984 5829 CHECK 5695 4669 CHECK 1537 1506 CHECK 1219 4651 CHECK 3586 9338 CHECK 2397 12137 JOIN 10382 7682 CHECK 8532 893 JOIN 2943 484 CHECK 6798 1293 CHECK 8493 2545 CHECK 9314 1429 CHECK 2893 4488 CHECK 6508 6463 CHECK 6231 12245 CHECK 23 6926 CHECK 9647 4157 CHECK 5378 11777 JOIN 11156 10189 CHECK 7118 6923 CHECK 10591 11836 CHECK 7741 2306 CHECK 9360 4949 CHECK 8624 9227 CHECK 6227 11572 JOIN 7123 1941 CHECK 144 9066 CHECK 11950 4787 CHECK 7672 184 CHECK 1631 5553 CHECK 7406 1751 CHECK 2727 4348 CHECK 11838 1511 CHECK 1056 11544 CHECK 12021 12243 CHECK 9634 283 CHECK 900 1280 CHECK 4719 10426 CHECK 1440 4047 CHECK 9609 8684 CHECK 3600 10076 CHECK 4152 9515 CHECK 8660 5677 CHECK 798 6330 CHECK 2655 10137 CHECK 940 12008 CHECK 8454 9707 JOIN 154 10485 CHECK 638 6337 CHECK 5033 4792 CHECK 11857 11338 CHECK 2641 9623 CHECK 7347 11684 CHECK 1465 2667 CHECK 10615 1663 CHECK 10134 2774 CHECK 2734 2286 CHECK 4055 6504 CHECK 7739 12128 CHECK 11822 7052 CHECK 4006 1572 CHECK 6599 10357 CHECK 9102 985 JOIN 8996 6380 CHECK 4997 2993 CHECK 6767 5506 CHECK 3609 11801 CHECK 11864 12239 CHECK 10716 5830 CHECK 9564 3367 CHECK 9034 9090 CHECK 8321 3523 CHECK 5416 9692 CHECK 10432 10844 CHECK 10285 2245 CHECK 9729 10006 CHECK 3191 225 CHECK 7983 3039 CHECK 7523 10700 CHECK 250 3695 CHECK 3796 9421 CHECK 9088 10506 CHECK 5857 8266 CHECK 1810 329 CHECK 8917 10996 CHECK 8234 1707 CHECK 8239 7057 CHECK 10350 8314 CHECK 6879 5431 CHECK 3164 5676 CHECK 11967 6038 CHECK 9511 5855 CHECK 7463 5939 CHECK 9074 979 CHECK 3330 12202 CHECK 3994 1026 CHECK 5784 9156 CHECK 4798 10552 CHECK 2687 1238 CHECK 3234 2136 CHECK 10382 1771 CHECK 5589 2974 CHECK 10938 8506 CHECK 3184 3012 CHECK 5059 9574 CHECK 12196 6595 CHECK 565 1052 CHECK 8622 965 CHECK 4094 5877 CHECK 8872 7023 CHECK 5137 6831 CHECK 5673 5745 CHECK 846 6907 CHECK 3236 6966 CHECK 11876 2951 CHECK 4291 2018 CHECK 10126 3846 CHECK 2016 7872 CHECK 1157 4719 CHECK 5287 9275 CHECK 6003 2145 CHECK 8839 8326 CHECK 12001 10405 JOIN 4795 1991 CHECK 3551 5532 CHECK 2205 5692 CHECK 5005 1507 CHECK 9984 3760 CHECK 4461 6050 CHECK 9272 10790 CHECK 6388 10771 CHECK 6450 5610 CHECK 4409 5193 CHECK 5638 7935 CHECK 4538 4345 CHECK 10287 10390 CHECK 1472 7838 CHECK 6268 10679 CHECK 7516 2800 CHECK 2562 7813 CHECK 11211 617 CHECK 7186 3621 CHECK 2912 7177 CHECK 8510 1417 CHECK 820 8380 CHECK 2119 8042 CHECK 1206 10270 CHECK 7611 8833 CHECK 6354 6645
0
|
|
|
|
| 21.06.2020, 14:40 | |
|
иВаН0301, а ты попроще примера не мог найти?
0
|
|
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
||
| 21.06.2020, 17:57 | ||
|
иВаН0301, У меня СНМ всего на 1000 максимум, увеличить размер массива до скольки хочешь
0
|
||
Сообщение от Super-Hacker
|
0 / 0 / 0
Регистрация: 18.06.2020
Сообщений: 17
|
|
| 21.06.2020, 19:32 [ТС] | |
|
Ну просто задача легкие тесты проходит, а большие нет
0
|
|
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
|||||||
| 21.06.2020, 23:07 | |||||||
|
иВаН0301, Ну я дже написал,
0
|
|||||||
|
Вездепух
  
13189 / 6824 / 1822
Регистрация: 18.10.2014
Сообщений: 17,267
|
||
| 21.06.2020, 23:29 | ||
Обычно эту операцию реализуют нерекурсивно, и обычным циклическим проходом по цепочке поиска. Отказавшись от рекурсивной реализации мы теряем возможность исправить все parent[ v ] вдоль пути поиска на конечную точку поиска. Но на самом деле это и не обязательно. Достаточно эффективным является решение, которое циклически пробегает вдоль всего пути поиска и просто исправляет parent[v] на parent[parent[v]]. То есть цепочки ссылок при каждом проходе укорачиваются "примерно в два раза".
0
|
||
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
|||||||
| 21.06.2020, 23:34 | |||||||
0
|
|||||||
|
Вездепух
13189 / 6824 / 1822
Регистрация: 18.10.2014
Сообщений: 17,267
|
|||||||
| 21.06.2020, 23:58 | |||||||
parent[v]. Важная "прелесть" вашего исходного (рекурсивного) варианта заключается именно в том, что он не просто ищет корень дерева, он еще и исправляет ссылки вдоль пути поиска, тем самым уменьшая высоту дерева и повышая эффективность последующих операций поиска. Именно поэтому "классическое" решение этой задачи - компромисс между этими двумя крайностями: мы циклически пробегаем по пути поиска, но в то же время "немножко" исправляем ссылки parent[v] вдоль этого пути, по принципу parent[v] = parent[parent[v]].Что-то вроде
0
|
|||||||
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
|
| 22.06.2020, 14:04 | |
|
TheCalligrapher, Просто гениально, этим вы ничего не добились, ведь в оригинале parent[v] = find_set(v);
0
|
|
|
Вездепух
13189 / 6824 / 1822
Регистрация: 18.10.2014
Сообщений: 17,267
|
||
| 22.06.2020, 14:23 | ||
Я же ясно сказал: за дикую рекурсию parent[v] = find_set(v); - бить по рукам и больно. Как делать правильно, и почему это правильно - я подробно описал выше. Такое постепенное транзитивное замыкание, как в моем примере - все таки хрестоматийная классика программирования, а не мое изобретение.
0
|
||
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
|
| 22.06.2020, 14:26 | |
|
TheCalligrapher, Тогда сами выбирайте, O(1) (но при этом вы делаете это рекурсивно) или O(log(size)) (пацанский способ через цикл)
0
|
|
|
Вездепух
13189 / 6824 / 1822
Регистрация: 18.10.2014
Сообщений: 17,267
|
||
| 22.06.2020, 14:49 | ||
Ваш вариант в терминоглогии Тарьяна называется "сжатием путей" (path compression). Это имеет смысл в том случае, если поисковые запросы будут в конечном итоге сделаны "почти ко всем" элементам множества, возможно по нескольку раз. Потратив время на сжатие путей (никакое не O(1) разумеется, а намного больше) вы превратите дерево в куст, запросы к которому впоследствии будут действительно обрабатываться за O(1). Мой вариант в терминологии Тарьяна называется "уполовиниванием путей" (path halving). Он в конечном итоге тоже скомпрессирует пути, но только те, к которым будет сделано достаточно большое количество запросов. На те пути, к которым запросов нет (или мало), он время не тратит. В этом и заключается преимущество path halving в таких ситуациях. А уж что здесь лучше - зависит от задачи. В любом случае, ваш path compression лучше реализовывать на рекурсией, а просто двойным проходом по всему пути.
0
|
||
|
342 / 114 / 37
Регистрация: 26.11.2019
Сообщений: 735
|
||
| 22.06.2020, 15:04 | ||
0
|
||
|
Вездепух
13189 / 6824 / 1822
Регистрация: 18.10.2014
Сообщений: 17,267
|
||
| 22.06.2020, 15:15 | ||
И ещё раз повторяю: вариантов на самом деле три - path compression, path halving и path splitting - каждый из которых может являться оптимальным в своем наборе обстоятельств. Этот хрестоматийные азы программирования я не предлагаю здесь к обсуждению, а даю для обязательного изучения и запоминания. Пока вы не усвоите эти ценные знания, всерьез ваши рассуждения на эту тему принимать не получится.
0
|
||
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
| 22.06.2020, 15:15 | |
|
Помогаю со студенческими работами здесь
20
Поиск непересекающихся множеств Мощность пересечения множеств А и В(непересекающихся) Реализовать поиск непересекающихся множеств Поиск минимального острова с системой непересекающихся множеств Система уравнений теории множеств Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица.
Задача: зафиксировать три левых колонки в отчете.
Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка)
. . .
|
Настройки VS Code
Loafer 13.04.2026
{
"cmake. configureOnOpen": false,
"diffEditor. ignoreTrimWhitespace": true,
"editor. guides. bracketPairs": "active",
"extensions. ignoreRecommendations": true,
. . .
|
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2.
Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива.
Было так:. . .
|
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2.
Задача: реализовать контроль корректности заполнения дат назначения. . .
|
|
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html
Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
|
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2.
Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
|
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях.
Задача: при копировании документа очищать определенные реквизиты и табличную. . .
|
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий
anaschu 08.04.2026
https:/ / github. com/ shumilovas/ med2. git
main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели
8ATzM_2aurI
|
Наверх