1. Идея

Дана матрица isConnected, где:

• isConnected[i][j] = 1, если города i и j соединены дорогой напрямую;
• isConnected[i][j] = 0, если напрямую не соединены.

Нужно найти количество провинций — то есть количество групп городов, в каждой из которых из любого города можно добраться до любого другого, возможно, через промежуточные города.

По сути, задача сводится к поиску числа компонент связности в неориентированном графе:

• вершины — города;
• ребро между i и j есть, если isConnected[i][j] = 1.

Тогда ответ — это количество компонент связности.
Самый естественный способ найти его — запускать обход графа (DFS или BFS) из каждой ещё не посещённой вершины. Каждый такой запуск находит ровно одну новую провинцию.

2. Наблюдения

Наблюдение 1. Матрица задаёт неориентированный граф

Если город i соединён с городом j, то и j соединён с i.
Значит, граф неориентированный, а матрица симметрична.

Наблюдение 2. Провинция = компонента связности

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

Наблюдение 3. Из матрицы не нужно строить список рёбер

Можно обходить граф прямо по матрице:

• находим город v;
• просматриваем всю строку isConnected[v];
• если isConnected[v][u] = 1 и u ещё не посещён, продолжаем обход из u.

Это удобно и достаточно эффективно для данной формы входных данных.

3. Алгоритм

Будем использовать DFS.

1. Пусть n — число городов.
2. Создадим массив visited длины n, изначально все значения False.
3. Заведём переменную answer = 0.
4. Для каждого города i:
   • если visited[i] = False, значит найден новый ещё не обработанный компонент связности;
   • увеличиваем answer на 1;
   • запускаем DFS из i, отмечая все достижимые города как посещённые.
5. После завершения цикла answer и будет числом провинций.

Как работает DFS

Для вершины v:

• помечаем её как посещённую;
• перебираем все города u от 0 до n - 1;
• если isConnected[v][u] = 1 и u ещё не посещён, рекурсивно запускаем DFS из u.

4. Почему это работает

Докажем корректность алгоритма.

Рассмотрим момент, когда внешний цикл дошёл до города i.

Случай 1. i уже посещён

Это означает, что ранее был запущен DFS из некоторого города той же компоненты связности, и во время этого обхода до i уже добрались.
Значит, город i принадлежит уже учтённой провинции, увеличивать ответ не нужно.

Случай 2. i ещё не посещён

Тогда ни один из предыдущих обходов не мог попасть в i.
Следовательно, город i находится в новой, ещё не учтённой компоненте связности.

После увеличения answer запускается DFS из i. По определению DFS посетит:

• все вершины, достижимые из i;
• и только их.

Но множество всех достижимых из i вершин — это ровно вся компонента связности, содержащая i.
Значит, один запуск DFS полностью находит одну провинцию и помечает все её города.

Таким образом:

• каждая провинция будет учтена ровно один раз;
• лишних увеличений ответа не произойдёт.

Следовательно, итоговое значение answer равно числу провинций.

5. Сложность

Пусть n — число городов.

Время

Для каждой вершины при обходе мы просматриваем всю строку матрицы длины n.
Так как вершин n, общая сложность:

O(n²)

Память

• массив visited — O(n);
• рекурсивный стек DFS в худшем случае — O(n).

Итого:

O(n) дополнительной памяти.

CPP

#include <iostream>
#include <vector>

using namespace std;

void dfs(int v, const vector<vector<int>>& isConnected, vector<int>& used) {
    used[v] = 1;
    int n = (int)isConnected.size();
    for (int to = 0; to < n; ++to) {
        if (isConnected[v][to] == 1 && !used[to]) {
            dfs(to, isConnected, used);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> isConnected(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> isConnected[i][j];
        }
    }

    vector<int> used(n, 0);
    int provinces = 0;

    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            ++provinces;
            dfs(i, isConnected, used);
        }
    }

    cout << provinces << '\n';
    return 0;
}

PYTHON

import sys

sys.setrecursionlimit(10**7)

def dfs(v, is_connected, used):
    used[v] = True
    n = len(is_connected)
    for to in range(n):
        if is_connected[v][to] == 1 and not used[to]:
            dfs(to, is_connected, used)

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    is_connected = [[int(next(it)) for _ in range(n)] for _ in range(n)]

    used = [False] * n
    provinces = 0

    for i in range(n):
        if not used[i]:
            provinces += 1
            dfs(i, is_connected, used)

    print(provinces)

if __name__ == "__main__":
    main()