Проверьте, можно ли посетить все узлы неориентированного графа с данного узла.

Дан неориентированный граф , состоящий из N узлов, помеченных от 0 до N – 1 , которые представлены двумерным массивом arr[][] , где arr[i] представляет все узлы, подключенные к i ^-му узлу, задача чтобы узнать, можем ли мы посетить все узлы из узла X .

Примеры:

Input: arr = { { 1, 2 }, { 0, 3, 2 }, {0, 1}, {1} }, N = 4, X = 0
Output: YES
Explanation: As can be seen from the below graph, we can reach to any node from node 0.

The structure of the above graph

Input: arr = { { 1, 2 }, { 0, 3, 2 }, {0, 1}, {1} }, N = 5, X = 4
Output: NO
Explanation: No node is connected to the node 4.

Подход с использованием BFS:

The idea is to use BFS from starting from node X and count all the nodes that are visited in the path. Finally check if number of nodes that are visited are equal to given number of node N or not. If they are equal then print YES, otherwise NO.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Данный массив действует как список смежности n графа.
• Инициализируйте очередь и посещенный массив, поместите начальный узел X в очередь и пометьте его как посещенный.
• Инициализируйте переменную count для подсчета количества узлов, посещенных во время BFS.
• Выполните следующие действия, пока размер очереди больше 0
  • Вытолкните верхний узел (скажем, curr ) узел из очереди и увеличить счетчик на 1.
  • Исследуйте все дочерние узлы текущего узла
    • Проверьте, посещались ли дочерние элементы текущего узла, если нет, то поместите его в очередь и отметьте его как посещенный.
• Наконец, проверьте, равен ли count заданному N ,
  • Если верно, выведите YES
  • иначе выведите НЕТ

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N + E), где N — количество узлов, а E — количество ребер.
Вспомогательное пространство: O(N)