Используя язык программирования C++ или Python, напишите программу, которая позволяет определить количество государств

Суть вопроса: Определение количества государств на острове

Пояснение: Для решения данной задачи, мы можем использовать алгоритм поиска в глубину (DFS) или алгоритм поиска в ширину (BFS). Первым шагом мы инициализируем переменную "количество государств" как 0. Затем мы проходим по каждому городу на острове и, если этот город ещё не был посещён, запускаем алгоритм поиска в ширину или в глубину из этого города. В процессе обхода мы помечаем все достигнутые города как посещённые и увеличиваем счётчик государств на 1. В конце обхода, мы получаем общее количество государств на острове.

Например: Предположим, у нас есть следующая матрица смежности для городов острова:

[

  [0, 1, 0, 1],

  [1, 0, 1, 0],

  [0, 1, 0, 1],

  [1, 0, 1, 0]

]

В данном случае, у нас есть 2 государства на острове.

Совет: Чтобы лучше понять алгоритмы поиска в глубину и в ширину, вы можете визуализировать остров и дороги между городами. Можете посмотреть на примеры работы этих алгоритмов для лучшего понимания того, как они работают и почему они помогут нам в решении данной задачи.

Задание: Дана следующая матрица смежности:

[

  [0, 1, 0, 1],

  [1, 0, 1, 1],

  [0, 1, 0, 0],

  [1, 1, 0, 0]

]

Сколько государств находится на этом острове?