| 1 Шохрух Нарзуллаев, 16 июня 2025 г. 18:39:00 |
| Наконец-то разобрался, оказывается действительно не нужно отдельно рассматривать корневой узел графа. решил за 0.062 сек. Использовал fread/fwrite в C++.
|
|
|
| 2 Шохрух Нарзуллаев, 16 июня 2025 г. 15:14:35 |
| Решил по видео разбор Меньшикова. Но так и не понял ошибку своего реализацию(. У него раз и работает, у меня нет) Не понял почему отдельно рассматривается корневой узел, там точка сочленения по другому вычисляется.
|
|
|
| 3 Яндулов Богдан, 09 июня 2020 г. 20:40:11 |
| SQRT-декомпозиция + СНМ с откатами как вариант)
|
|
|
| 4 Винк В В, 11 ноября 2018 г. 11:03:56 |
| Достаточно одного обхода в глубину всех вершин и рёбер. Для быстрого поиска номеров рёбер для каждой вершины использовал два дополнительных массива. Заполнил их до первого вызова рекурсивной функции. Получилась конструкция типа a[b[c[i]]]. Время <= 0.186 сек.
|
|
|
| 5 Фоменко Владимир, 20 августа 2012 г. 14:30:11 |
| Что за сервер, что за 5 секунд не проходит n^2 ? Да уж...
|
|
|
| 6 Пересадин Илья, 13 января 2012 г. 15:21:10 |
| вроде бы относительно непростая задача, а решается за О(n+m)
|
|
|
| 7 Каменко&Барышев, 21 августа 2011 г. 20:31:56 |
| Точки сочленения + небольшая модификация работает примерно за o(n+m) :)
|
|
|
| 8 NikitOsya, 13 апреля 2011 г. 11:18:09 |
Не пойму как уложиться по времени( Первое и последнее что пришло в голову это наиполнейший перебор, но подсчитав сколько это будет работать (~31 год) я, мягко говоря, разочаровался...
Подскажите плз кто решил)
|
|
|
| 9 VictoR Yegorov, 03 апреля 2011 г. 22:58:10 |
| Я правильно понимаю, что сложность порядка O(N^2+NM) и нужно уменьшать константу?
|
|
|
| 10 Федюнин Валерий Викторович, 04 марта 2011 г. 10:47:53 |
| Поиск точек сочленения точно правильный, отсылал его в 2 разных контеста, но тут ВА8((
|
|
|
| 11 Федюнин Валерий Викторович, 04 марта 2011 г. 9:43:08 |
| Даже отсылал на задачу поиск количества точек сочленения, там этот исходник получил ОК...
|
|
|
| 12 Нагин Сергей Юрьевич, 08 апреля 2009 г. 18:39:26 |
| Ну можно и свой написать... Тоже не проблемы... Хотя это труднее...
|
|
|
| 13 SOVA xxx, 08 апреля 2009 г. 10:39:03 |
в том что в яве стек стандартный 256 кб:) и граф 20000 вершин цепочкой просто нельзя обойто с таким стеком
вот я прошу чтобы в самом компиляторе проги запускали с параметром -Xss64m стек делает 64 метра его можно использовать и память при этом будет нормально отображаться у вас в состоянии системы:)
|
|
|
| 14 Нагин Сергей Юрьевич, 07 апреля 2009 г. 18:59:44 |
| А в чеём проблема в рекурсивном ДФС ??? Вроде-же все ясно...
|
|
|
| 15 SOVA xxx, 07 апреля 2009 г. 15:21:54 |
Сергей Николаевич раскажите пожалуста про стек в яве что у вас да как и желательно как его увеличить в проге или вообще тк в этой задаче я не могу пустить дфс даже сразу переполение стека)или же писать нерекурсивный дфс?
Ты вроде как сдал уже, с чем тебя и поздравляю. Я на яве не пишу, если что.
|
|
|
| 16 SOVA xxx, 07 апреля 2009 г. 15:06:53 |
Нагин догадацца нетрудно, трудно написать чтобы прошло
я уже два решения завалил....
|
|
|
| 17 SOVA xxx, 07 апреля 2009 г. 15:04:36 |
аааа как сдать эту задачу...
на яве нихватает стека на паскале памяти на плюсах одно из двух))))
а на бэсике и с я писать не умею)))
|
|
|
| 18 SOVA xxx, 07 апреля 2009 г. 14:02:02 |
| Хотя нет я ошибся такое решение по времени летит уже на 4000 вершин)
|
|
|
| 19 SOVA xxx, 07 апреля 2009 г. 12:53:48 |
имхо тут такая шняга:
идем циклом по вершинам
каждую по очереди делаем корнем графа
находим кол-во вершин в связных непересекающихся областях(всмысле от корня идут один или больше подграфов которые не имеют друг с другом инцидентных вершин т.е. путь есть тока через корень)а дальше уже чистая математика попробую систему непересекающихся сюда привинтить:)
|
|
|
| 20 Нагин Сергей Юрьевич, 06 апреля 2009 г. 22:05:11 |
| Да тут не просто точки сочлинения... Тут трабла сложная! А что если точка не есть точкой сочлинения и она не разбивает на несколько компонент. Тогда скорее всего для нее ответом будет Н-1 ... МОжет я и догадуюсь до решения... Но написать его крайне сложно... Связный список, топологичсекая сорт... и тд...
|
|
|
