Фильтрация вершин графа

Question

Скажем, у меня есть ориентированный ациклический граф с N вершинами и подмножество вершин на размер M.

Вершины M все помечены как посещенные, как можно найти все вершины, которые все их предшественников на графике посещают

например: если существует 4 вершины a, b, c, u и 3 ребра (a, u) (b, u) (c, u) и a, b, c отмечены как посещенные, мне нужно вывести u.

Я думал идти через все вершины и для каждой проверки вершины всех своих предшественников, но я думаю, что это не очень эффективное ..

Answer 1

Удалить эти M вершину из исходного графа. Это можно сделать, просто удалив исходящие ребра из «посещенных» узлов.

Узлы, которые не находятся в M и недоступны из любой другой вершины, имеют все их предшественники, посетившие (в M).

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