Страницы: 0 | 20 | 40 | (43) | 60 | 80 | показать все | след. страница
В ответ на:
Ну вот, кстати, о сортировках и их реализациях. Недавно проспорил другу пивасик, не смог написать qsort, который работает быстрее вставок на случайном массиве длины 100. Хотя оптимизации он мне разрешил юзать разные, например, короткие массивы (до 8ми) я сортировал его же функцией
Это как раз то, о чем я и говорил. Случайная реализация алгоритма не позволяет судить о самих алгоритмах. То, что предлагается меряться скоростью - это чистой воды задротство.
В ответ на:
Сначала ты предлагаешь разбивать на сильно связные компоненты и выдаешь это за решение, хотя никто не говорил, что эти компоненты большие и это сильно упростит задачу.
Во-первых, поскольку сложность операции линейная, это задачу точно не усложнит. А значит, это целесообразно. Во-вторых, это сразу позволяет свести задачу для произвольного графа к задаче для ациклического графа. Ну а в-третьих, пока еще никто в данном треде не предложил лучшего алгоритма.
Ладно, я начинаю думать и писать, ты бы тоже написал, полезно будет.
Quote:Это аргумент (пока индуктивный). Все остальное - нет.
Во-вторых, это сразу позволяет свести задачу для произвольного графа к задаче для ациклического графа
В ответ на:
Сначала ты предлагаешь разбивать на сильно связные компоненты и выдаешь это за решение, хотя никто не говорил, что эти компоненты большие и это сильно упростит задачу.
Решение было приведено ранее, вопрос в том, насколько оно хорошее. А разбиение на компоненты лишь потенциально может усложнить задачу в 2 раза, и только в том случае, если кто-то предложит линейный алгоритм, не использующий это разбиение. А этого пока никто не сделал.
В ответ на:
Ладно, я начинаю думать и писать, ты бы тоже написал, полезно будет.
Предлагаю подумать, какова была бы сложность решения задачи, если изначально было бы известно, что граф ациклический. Ясно, что сложность решения для произвольного графа не меньше сложности решения для ациклического. А тут, мне кажется, все плохо. Не получается придумать линейный алгоритм, а только квадратичный. Если вершин у нас порядка 10^6, то операций будет порядка 10^12.
Quote:
Не получается придумать линейный алгоритм, а только квадратичный.
Квадратичный алгоритм можно написать без заморочек: для каждой вершины делаем полный обход графа, выставляя флажки, и все.
Все-таки ты пояснишь, что там с двудольностью, циклами? Скажи уже все, что о нем знаешь наверняка.
А заморочки позволяют его сделать квадратичным лишь в самых плохих случаях.
Или там у тебя номера вершин как-то сильно раскиданы?
Quote:
в чем кстати смысл ребер в самих себя?
А такие есть? Вообще-то не должно быть. Граф совершенно точно двудольный. Про циклы четной длины - мой косяк, конечно же. Циклы могут быть. V примерно равно E, тоже правда.
Quote:
А такие есть? Вообще-то не должно быть. Граф совершенно точно двудольный. Про циклы четной длины - мой косяк, конечно же. Циклы могут быть. V примерно равно E, тоже правда.
первая же строчка
00000002 00000002
Ладно, граф двудольный. Т.е. постановка такая: в двудольном графе тарам пам-пам, так?
В общем виде действительно ничего хорошего не выйдет походу.
Quote:
В общем виде действительно ничего хорошего не выйдет походу.
его пример халявным алгоритмом где-то за минуту обсчитывается