На самом деле если бы я не знал, что существует алгоритм bipartite то догадаться сложно

Я не зря сказал про «покрасить в даа цвета»

Да они издеваются — https://leetcode.com/explore/challenge/card/june-leetcoding-challenge/ 😄

Да они издеваются — https://leetcode.com/explore/challenge/card/june-leetcoding-challenge/ 😄

🤣🤣🤣

Не отдохнуть

Это всё карантин этот, людям делать нечего. Уже жду недождусь когда закончится.

Пхах, не только вы

Мне кажется умру если не устрюсь в Я

Будет “Game over” перед лицом

А ещё визовые центры Британии открываются с 1 июня в Беларуссии и Украине, но не в России. Вай?! 😄

А ещё визовые центры Британии открываются с 1 июня в Беларуссии и Украине, но не в России. Вай?! 😄

Нэ европа

Нэ европа

Печаль-беда.

Вчерашнюю задачу вообще нереально без DFS BFS решить?

Я что-то в дискас зашел, там одни DFS BFS

Как я догадываюсь, это типикал задачка для дерева

https://leetcode.com/explore/featured/card/may-leetcoding-challenge/537/week-4-may-22nd-may-28th/3342/discuss/655026/Using-two-sets-with-out-graph

О! Питонист единомышленник!!1!

Вместе мы противостоим DFS и BFS захватчикам!

Вчерашнюю задачу вообще нереально без DFS BFS решить?

Ну да, для графов (и дерева в частности) это типично, я бы сказал только так и можно. Во вчерашней задаче правда надо знать алгоритм.

https://leetcode.com/explore/featured/card/may-leetcoding-challenge/537/week-4-may-22nd-may-28th/3342/discuss/655026/Using-two-sets-with-out-graph

Название интригует :-) решим вообще без графов 👍

Я так же решал

Я так же решал

🔥

Только… говно код и помощь гугла

И у меня очень грязный код был

Это было ужасно в общем

Но сейчас я приведу его в человеческий вид и покажу вам

@vitkarpov а у вас сколько строк дерево заняло?

Можете скинуть самое короткое решение с деревом? Мне для изучения

А то в discuss так плато текста

@vitkarpov а у вас сколько строк дерево заняло?

Там bfs в цикле, строк 15, наверное.

А то в discuss так плато текста

Полотна точно не должно быть :-)

Можете скинуть самое короткое решение с деревом? Мне для изучения

https://gist.github.com/vitkarpov/1b52efba1d0ea4dc4cbe79fad83b25e9

А какая complexity?

Лучше N^2 не может быть?

А какая complexity?

Ага, O(V^2), где V – количество узлов.

Быстрее, ну хз. Наверное, как-то можно 🙂

У меня вопрос

если память использовать дополнительную

А може быть такое, что будет [2,3] и при этом ни 2 ни 3 больше нигде не встречаться

Это не сломает алгоритм?

А може быть такое, что будет [2,3] и при этом ни 2 ни 3 больше нигде не встречаться

тогда вроде 2 и 3 можно разнести по разным группам легко

Логично

Вроде не ломает

Ладно, походу графы не мое

отличный фоллоу-ап сегодня 😂

отличный фоллоу-ап сегодня 😂

Уже страшно

Ладно, походу графы не мое

графы это отдельная большая тема, да. кстати, вчера отличный пост сделали на эту тему — https://leetcode.com/discuss/general-discussion/655708/graph-problems-for-beginners-practice-problems-and-sample-solutions

https://gist.github.com/vitkarpov/1b52efba1d0ea4dc4cbe79fad83b25e9

У меня почти так же https://leetcode.com/problems/possible-bipartition/discuss/655784/C-O(N%2BM)-BFS-solution

В общем

Из O(govnoCode) сделал O(log(govnoCode))

https://pastebin.com/uqiXqdwe

И получилось короче чем у питонистов

И получилось короче чем у питонистов

А rest за что отвечает?

Понял, убирает те пары, которые на данный момент не подходят "на потом"

Понял, убирает те пары, которые на данный момент не подходят "на потом"

Да да

Это было самое сложное

А как это решение по времени?

Вот честно не знаю, но скорее всего N ^ 2

Ага, O(V^2), где V – количество узлов.

.

Это если ВСЕ узлы не связанны

И мы будет по 1 каждую итерацию убирать

Ну, там же по дефолту убирается 1, а остальные “на потом“

Хм.. А rest у нас не обнулится (9), когда мы на очередной заход (4) пойдём?

номера строк

Обнулиться

По скобкам сложно сориентироваться

Оно же уничтожается в конце цикла

аа

точно, мы же его в dislikes скопировали, всё

Оно же уничтожается в конце цикла

+ ре декларуется

Да, работает на чуде

Да уж. "Рассовываю пока могу, а если не могу, с остатками разберусь потом снова"

:)

Спонсор решения не на деревьях — “Не любовь Данила к деревьям! Не любовь к деревьям – что угодно лишь бы не DFS или BFS. Hate greenpiece!”

Зелёные не одобряют)

Да уж. "Рассовываю пока могу, а если не могу, с остатками разберусь потом снова"

Ну по сложности так же, так что нормально))0)

А если вместо unordered_set сделать set, то операция count будет за логарифм работать, а не за линию

в худшем случае

Какая-то херня

Я не считаю что может быть линейная