|
|
|
|
|
|
|
| 1 Неизвестный, 27 ноября 2025 г. 21:25:03 |
| Gon and Killua are Kurapika's friends
|
|
|
| 2 Неизвестный, 27 ноября 2025 г. 18:18:49 |
| Так что лучше запускать BFS с каждой вершины и проверять встречался ли это вершина больше чем один раз в этом BFS и всё ответ готов
|
|
|
| 3 Неизвестный, 27 ноября 2025 г. 18:18:01 |
| Ну просто ищите есть ли цикл в графе и всё.И если есть то тогда просто выводите "No",в ином случае выводите "Yes"
|
|
|
| 4 Бончев Максим Владимирович, 01 сентября 2019 г. 21:34:27 |
| Денис, это не важно. Главное что б все условия прапорщика были соблюдены.
|
|
|
| 5 Маркелов Денис Дмитревич, 09 февраля 2018 г. 12:07:55 |
| тесты показывают, что достаточно проверить на ацикличность, а как 3 2 1 2 3 2 Кто выше 1 или 3 ?
|
|
|
| 6 Зинов Вадим Игоревич, 10 октября 2014 г. 23:11:59 |
| Луффи, спасибо за упоминание о "черных точках" очень помогло.
|
|
|
| 7 Луффи, 07 октября 2014 г. 17:19:31 |
Изначально все вершины «белые». Из каждой вершины проводим обход в глубину.
При входе в вершину делаем её «серой», при выходе — «чёрной» и одновременно заносим в окончательный список.
Если вдруг вошли в серую вершину — найден цикл, топологическая сортировка невозможна.
|
|
|
| 8 Захаров Константин Леонидович, 05 декабря 2013 г. 18:09:43 |
Топсорт с емакса конечно копируется неплохо, но, чисто для справки - можно еще фордом беллманом, правда уже несовсем так, как на емаксе) Кстати, кто хочет прикрутить восстановление ответа и нитащит - попробуйте тест
5 4
1 2
3 2
3 4
5 4
у меня вообще выводило 1 2 3 4 5 с первоначальной версией (бфс из вершин где parent[v] == -1), но удалось пофиксить.
|
|
|
| 9 Настенька, 19 ноября 2012 г. 15:24:09 |
А что за наркоманские решения: искать циклы, топологическую сортировку использовать? Тут всё намного проще и завязано на одном из легчайших алгоритмов на графах (спойлерить уж не буду)
Куда еще проще? Поделитесь с народом.
|
|
|
| 10 Настенька, 19 ноября 2012 г. 15:23:00 |
| С первого раза минут за десять. Воохууу, сегодня мой день
|
|
|
| 11 Гераськин Егор Владимирович, 29 сентября 2012 г. 22:59:51 |
Тупо проверка графа на ацикличность:)
Да
|
|
|
| 12 Сафронов Евгений Сергеевич, 09 июля 2012 г. 7:43:35 |
Распространённая задача на топологическую сортировку — следующая. Есть n переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить, что это в точности и есть задача о поиске топологической сортировки в графе из n вершин.
=)
Но про искать циклы - верно. Невозможно составить топологическую сортировку, если в графе есть циклы. Но нам нужна не сама сортировка, а лишь проверка на ее возможность, так что 62% - многовато...
Согласен, процент завышен. Но не сильно. Всякая задача с рекурсией - это минимум 45% на данном сайте.
|
|
|
| 13 Терешин Роман Юрьевич, 21 марта 2012 г. 13:56:28 |
| В 12 тесте (возможно, и в других также) входные данные допускают повтор пар. В терминах задачи это означает, что прапорщик о некоторых парах солдат знает одно и тоже несколько раз - удивительная вещь (одновременное присутствие упорядоченной пары и пары, ей обратной в виду не имеется - это вполне корректная ситуация, ответ на вход, содержащий подобное - "No"). Для реализации это означает следующее - если вы выбираете список смежности для представления графа в памяти, а каждый из списков реализуете массивом, "знающим" свой размер - учтите, что при получении входных данных вы можете столкнуться с тем, что вершина может иметь более N - 1 соседей - камень в огород составителей тестов.
|
|
|
| 14 Жиркевич Анастасия Борисовна, 01 февраля 2012 г. 23:35:28 |
Кто еще думает, каким алгоритмом воспользоваться, рекомендую алгоритм ФЛОЙДА-УОРШЕЛЛА. Находка Википедии... просто супер - короче алготма я еще не видела. А на ацикличность проверку сделать легко: проверьте есть ли на диагонали не нули))) и ACCEPTED
Возможно, если искать не наикратчайшие расстояния, а наидлиннейшие.
|
|
|
| 15 Балакший Андрей Владимирович, 24 октября 2011 г. 20:56:41 |
| Все таки делал по-честному, при отправке лишь закомментил вывод топ.сортировки. Но все равно много процентиков, даже слишком....
|
|
|
| 16 Пересадин Илья, 26 августа 2010 г. 19:25:07 |
| интересней было бы, если бы требовалось вывести построение... а то можно просто на ацикличность проверить и не париться
|
|
|
| 17 Ким Вячеслав Олегович, 06 февраля 2010 г. 14:02:56 |
| Надо бы задачу, чтоб все построение выводить надо было.
|
|
|
| 18 Демиденко Виталий, 15 марта 2009 г. 20:11:22 |
| Если есть цикл, то No, иначе построение возможно. С таким решением прошло.
|
|
|
| 19 Akzholov Darhan Bektenovich, 07 марта 2008 г. 21:10:00 |
А что если искать циклы? Если есть цикл то - NO else YES ?
Да, можно.
|
|
|
| 20 Беляев Игорь (<-UnderFelixAbove->) 21 год, 19 января 2008 г. 1:28:55 |
Топологическая сортировка нынче в цене).
Да, типа того.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
