2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Количество пар с общим предком в произвольном графе
Сообщение17.09.2015, 09:55 


08/09/13
141
Вершины $v$ и $u$ имеют общего предка если существует вершина $w$ такая, что из неё достижимы $v$ и $u$.
Для данного ориентированного графа найти количество различных пар $(v,u)$ таких, что $v$ и $u$ имеют общего предка.
$1 \le N \le {10}^{4}$ ($N$ - количество вершин, $M$ - количество рёбер)
Time limit: 1.2 seconds

Ясно, что прежде всего нужно вычислить конденсацию. А вот дальше не ясно.
Много всяких идей перебрал, начинал с подзадачи типа "в каждой вершине ацикличного графа записано число, найти для каждой вершины сумму во всех её предках". Эту задачу решить не смог, да и сведение к основной оказалось неверным...
Кажется, что следует обрабатывать наименьшие вершины (без входящих рёбер) одну за другой.
Например, из первой наименьшей вершины сделали dfs, получили что достижимо $t$ вершин (суммируем количество реальных вершин в каждой вершине конденсации), значит, есть уже $t^2$ пар. Потом следующие делаем dfs из новых минимальных вершин и каждый раз получаем некоторое дерево. В этом дереве будут вершины, уже виданные в предыдущих dfs-ах и будет два числа $s$ - количество вершин, уже виданных и $t$ - количество новых вершин. Понятно, что к ответу надо добавить $st+t^2$.
Вот только сталкиваемся с проблемой - при новом dfs если мы встретили уже виданную вершину, то надо обламывать dfs и не идти дальше по рёбрам из этой вершины. А для этого надо хранить в каждой уже виданной вершине количество её предков, что уже является вариантом подзадачи, которую я приводил выше. При этом мы можем наткнуться на две виденных вершины, одна из которых является предком другой или просто множество достижимых из них вершин пересекаются и тут уж непонятно что делать.

В общем, я запутался и прошу помощи.

-- 17.09.2015, 09:00 --

Прошу прощения, промахнулся с разделом. Переместите, пожалуйста, в "Олимпиадные задачи CS"

 Профиль  
                  
 
 Re: Количество пар с общим предком в произвольном графе
Сообщение17.09.2015, 12:13 
Заслуженный участник
Аватара пользователя


01/09/13
1269
Как кажется, надо строить конденсированный граф - как при этом считать циклы и цепи вроде бы понятно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group