Карта проезда программиста Васи представлена в виде матрицы смежности графа. Необходимо написать программу, которая

Задача: Карта проезда программиста Васи

Объяснение:

Для решения данной задачи мы можем использовать алгоритм обхода графа в ширину (BFS - Breadth-First Search).

Сначала нам необходимо прочитать количество городов N. Затем мы считываем матрицу смежности графа, где каждый элемент a[i][j] соответствует существованию дороги между городами i и j. Если дороги существует, a[i][j] будет равно 1, в противном случае - 0.

После этого мы инициализируем массив visited, который будет отслеживать города, которые были посещены. Мы помечаем первый город, как посещенный, и добавляем его в очередь.

Пока очередь не пуста, мы извлекаем первый элемент, проверяем, существуют ли дороги из него в другие города, и если да, то добавляем непосещенные города в очередь и помечаем их как посещенные.

В конце, если все города были посещены, мы выводим "YES", иначе - "NO".

Например:

*Входные данные:*

5

0 1 1 0 0

1 0 1 0 0

1 1 0 1 1

0 0 1 0 0

0 0 1 0 0

*Выходные данные:*

YES

Совет:

Чтобы лучше понять решение этой задачи, можно нарисовать граф и представить города в виде вершин, а дороги - в виде ребер. Также стоит обратить внимание на принцип работы алгоритма BFS, который пошагово обходит все вершины, начиная с начальной.

Дополнительное задание:

Попробуйте решить задачу самостоятельно. На входные данные:

4

0 1 0 0

1 0 1 0

0 1 0 1

0 0 1 0

Ожидаемый вывод:

NO