Обнаружение стока в ориентированном ациклическом графе

Предположим, что есть одна вершина со следующим свойством в DAG :

  1. Все вершины соединены с ней

  2. Это не , соединенный с любой вершиной

Обычно это называется сток-вершиной .

Можно ли обнаружить эту вершину в O (n) , где n - это количество вершин в графе?

5
задан nbro 27 July 2015 в 19:03
поделиться