Предположим, вам дан неориентированный граф G с n вершинами и m ребрами, представленными списком смежности A, и вам также дано подмножество вершин S с размером | S | представлены массивом. Как вы можете проверить, является ли S вершинным слоем G с O (n + m) временем и O (n + m) пространственной сложностью?
Это дополнительный вопрос к вопросу, который Я отправил ранее на этой неделе, здесь . Это может помочь сначала прочитать этот пост (и решение) там.
По определению покрытия вершин я знаю, что мы требуем, чтобы каждое ребро было инцидентным той вершине, которая содержится в S.
Я пытался следовать подходу, аналогичному тому, который я опубликовал в предыдущей теме. В частности, я создал массив B [], содержащий все вершины, которые есть в G, но не в S. Это означает, что для любых двух вершин u и v в B, если (u, v) существует, то покрытие вершин не действительно.
Но я почти уверен, что этот алгоритм равен n ^ 2, а не n + m, поскольку, если S - пустое множество, то B будет содержать все вершины, а если G - полный граф, то проверяется, является ли ( u, v) существует операция O(n^2).
Мне было интересно, есть ли хорошее решение этой проблемы.
Спасибо