Количество пар с общим предком в произвольном графе

[fractalon]

Вершины $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"

[Geen]

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