Предположим, что есть одна вершина со следующим свойством в DAG
:
Все вершины соединены с ней
Это не , соединенный с любой вершиной
Обычно это называется сток-вершиной .
Можно ли обнаружить эту вершину в O (n)
, где n
- это количество вершин в графе?