00:01:16.435,00:01:19.435 Минко Марков: коректност? 00:01:19.759,00:01:22.759 Минко Марков: на Kahn 00:01:45.793,00:01:48.793 Минко Марков: ?? 00:01:46.230,00:01:49.230 Траян Господинов: противното 00:01:46.687,00:01:49.687 Марио Марков: Инварианта на цикъла от ред 14 00:04:25.185,00:04:28.185 Минко Марков: ?? 00:04:33.635,00:04:36.635 Минко Марков: ?? 00:04:39.716,00:04:42.716 Минко Марков: ???? 00:04:45.261,00:04:48.261 Минко Марков: ?? ?? ?? ?? 00:04:51.454,00:04:54.454 Марио Марков: Ами.. с всяко достигане на ред 14 в Т сме въвели правилно всички източници, “отразени” в А от предходното достигане, а в А е “отразявен” графът без тях 00:04:55.766,00:04:58.766 Христо Терзийски: T[1..k] е dag 00:04:56.440,00:04:59.440 Минко Марков: ?? ?? ?? ???? ?? ?? ?? 00:04:57.899,00:05:00.899 Марио Марков: Нещо такова на първо четен чи идва 00:05:17.425,00:05:20.425 Марио Марков: “Отразен” вместо “отразявен” 00:05:53.609,00:05:56.609 Ивайло Арнаудов: T[1..k] е топологическо сортиране на някакъв подграф един вид 00:06:46.779,00:06:49.779 Александър Велинов: МПД? 00:07:28.350,00:07:31.350 Ивайло Арнаудов: върховете, които са черни 00:07:39.916,00:07:42.916 Ивайло Арнаудов: т.е взимаме тях и правим подграф 00:08:42.151,00:08:45.151 Ивайло Арнаудов: да, да 00:08:57.814,00:09:00.814 Марио Марков: Не трябва ли да кажем и нещо за А и за S 00:09:07.479,00:09:10.479 Марио Марков: За да скалъпим доказателството 00:09:12.363,00:09:15.363 Александър Велинов: Можем ли да кажем "индуцирана верига"? 00:12:24.583,00:12:27.583 Минко Марков: става ли така? 00:12:27.252,00:12:30.252 Траян Господинов: да 00:12:45.444,00:12:48.444 Марио Марков: Да видях го 00:12:59.084,00:13:02.084 Минко Марков: верига?? 00:13:19.588,00:13:22.588 Александър Велинов: Ясно 00:13:21.388,00:13:24.388 Александър Велинов: Мерси 00:15:20.888,00:15:23.888 Минко Марков: 4,5,6 са n+m 00:15:29.681,00:15:32.681 Минко Марков: нали?? 00:15:33.463,00:15:36.463 Марио Марков: Да 00:15:33.642,00:15:36.642 Александър Велинов: да 00:15:48.219,00:15:51.219 Христо Терзийски: а защо казахте, че не може бързо да се намерят върховете, които са източници 00:15:49.910,00:15:52.910 Минко Марков: НЕ СЕ ПОЛУЧАВА като n (m) 00:16:17.206,00:16:20.206 Минко Марков: n+m 00:16:45.065,00:16:48.065 Христо Терзийски: това не ги ли намира 00:18:38.288,00:18:41.288 Христо Терзийски: да 00:18:44.990,00:18:47.990 Траян Господинов: принципно ако реализацият ание е vector > може 4, 5, 6 да са O(n) 00:19:48.203,00:19:51.203 Александър Велинов: да 00:19:51.229,00:19:54.229 Симеон Николов: да 00:20:06.209,00:20:09.209 Траян Господинов: защото имаме константо .size() 00:20:14.730,00:20:17.730 Траян Господинов: И знаем graph[1] колко върха има 00:20:15.320,00:20:18.320 Иван Ганев: това е out degree 00:20:35.700,00:20:38.700 Иван Ганев: Няма как за по-малко от от o(n + m) 00:20:46.829,00:20:49.829 Траян Господинов: то ги има като размер 00:21:11.568,00:21:14.568 Марио Марков: Пак трябва да ги обходиш 00:21:17.931,00:21:20.931 Иван Ганев: Размерът на списъците е out degree-то на този връх 00:21:23.584,00:21:26.584 Марио Марков: Какво значение има че знаеш колко са 00:21:38.005,00:21:41.005 Траян Господинов: ясно че трябва за 14-24 00:21:45.566,00:21:48.566 Траян Господинов: ама принципно говоря :D 00:21:55.818,00:21:58.818 Траян Господинов: да да, ясно е 00:21:56.714,00:21:59.714 Минко Марков: ?? 00:24:50.455,00:24:53.455 Минко Марков: 2-оцв. чрез BFS 00:25:01.587,00:25:04.587 Минко Марков: 2-оцв чрез DFS 00:26:09.586,00:26:12.586 Марио Марков: Да, отново алтернираме цветове с обхождането и ако един връх се окаже с два цвята гърмим 00:27:49.404,00:27:52.404 Траян Господинов: почваме всички върхове Undefined, започваме от връх start и го маркираме Even и тръгваме с дфс като редуваме Odd и Even и заместваме само Undefined. Ако попаднем на връх който е Odd и искаме да го направим Even (или обратно), значи не е двуоцветим 00:29:09.600,00:29:12.600 Александър Караиванов: Така излиза цикъл с нечетна дължина 00:33:24.496,00:33:27.496 Марио Марков: Ок е, виждат се стрелките 00:35:54.362,00:35:57.362 Минко Марков: ясно?? 00:36:00.268,00:36:03.268 Марио Марков: Да 00:36:13.865,00:36:16.865 Минко Марков: фактор-гр е даг? 00:36:52.042,00:36:55.042 Траян Господинов: ако не беше, тогава не сме направили добра факторизация нещо ;д 00:36:53.591,00:36:56.591 Христо Терзийски: иначе ще имаме по-малко силно свързани компоненти 00:37:06.830,00:37:09.830 Марио Марков: Да, че е насочен и че е граф е ясно... ако допуснем че има цикъл, ще излезне, че в оригиналния няколко свързани компоненти се сливат в една 00:43:34.766,00:43:37.766 Марио Марков: Проблемът ще е в ребрата, които сочат от една компонента в друга... ако алгоритъмът първо обходи връх от първата компонента, то ще излезне, че двете са свързани, защото рекурсивната функция ще премине от първата във втората... но ако започнем от връх във втората ще ги определи правилно като две отделни защото не може да премине в първат