1. Идея

Нужно посчитать количество связных компонент в неориентированном графе.

Что здесь является графом:

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

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

Значит, задача сводится к классическому действию:

• перебираем все вершины;
• если вершина ещё не посещена, запускаем из неё обход графа;
• все достигнутые вершины принадлежат одной провинции;
• увеличиваем ответ на 1.

В эталонном решении для обхода используется итеративный DFS через стек.

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

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

По условию isConnected[i][j] = isConnected[j][i], значит дорога двусторонняя. Это обычный неориентированный граф.

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

Если из земли A можно добраться до земли B, то они в одной провинции. Это и есть определение связности в графе.

Наблюдение 3. Из непосещённой вершины можно найти всю её провинцию

Если начать DFS из некоторой земли start, то обход посетит:

• саму start,
• все земли, в которые можно попасть по дорогам,
• и только их.

Значит, один запуск DFS полностью выделяет одну провинцию.

Наблюдение 4. Матрица смежности удобно обходится за O(n^2)

Для каждой вершины u мы просматриваем всю строку isConnected[u][0 ... n-1], чтобы понять, куда можно идти дальше.

Так как n <= 200, такой подход более чем достаточен.

3. Алгоритм

1. Считать n.
2. Считать матрицу isConnected размера n x n.
3. Создать массив used размера n, где used[i] показывает, посещали ли землю i.
4. Завести переменную provinces = 0.
5. Для каждой вершины start от 0 до n - 1:
   • если used[start] = true, пропускаем её;
   • иначе нашли новую провинцию:
     • увеличиваем provinces;
     • запускаем итеративный DFS:
       • кладём start в стек;
       • помечаем used[start] = true;
       • пока стек не пуст:
         • достаём вершину u;
         • перебираем все v от 0 до n - 1;
         • если isConnected[u][v] == 1 и used[v] == false, помечаем v и кладём её в стек.
6. Вывести provinces.

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

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

1. Каждый запуск DFS находит ровно одну провинцию

Пусть DFS запущен из земли start.

• Если существует путь от start до вершины v, то DFS сможет пройти по рёбрам этого пути и рано или поздно посетит v.
• Если вершина v была посещена DFS, значит существует цепочка переходов по дорогам от start до v, то есть v лежит в той же провинции.

Следовательно, DFS посещает в точности все земли из провинции, содержащей start.

2. Ни одна провинция не будет посчитана дважды

После запуска DFS все вершины найденной провинции помечаются как посещённые.

Когда внешний цикл дойдёт до любой другой вершины из этой же провинции, она уже будет отмечена в used, и новый запуск DFS не произойдёт.

Значит, одна провинция добавляет к ответу ровно 1.

3. Ни одна провинция не будет пропущена

Рассмотрим любую провинцию. В ней есть хотя бы одна вершина. Когда внешний цикл впервые дойдёт до какой-то вершины этой провинции, она ещё не будет посещена, потому что вершины из другой провинции не могут привести к ней при обходе.

Поэтому для этой провинции обязательно будет запущен DFS, и она будет учтена.

Вывод

Каждая провинция учитывается ровно один раз, значит итоговое значение provinces равно количеству провинций в империи.

5. Сложность

Пусть n — число земель.

Время

Для каждой посещённой вершины мы просматриваем всю строку матрицы длины n.

Всего вершин n, значит суммарная сложность:

• O(n^2)

Память

Используются:

• матрица isConnected размера n x n,
• массив used размера n,
• стек до n элементов.

Итого:

• O(n^2) памяти.

6. Код на C++17

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

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 start = 0; start < n; ++start) {
        if (used[start]) continue;

        ++provinces;
        stack<int> st;
        st.push(start);
        used[start] = 1;

        while (!st.empty()) {
            int u = st.top();
            st.pop();

            for (int v = 0; v < n; ++v) {
                if (isConnected[u][v] == 1 && !used[v]) {
                    used[v] = 1;
                    st.push(v);
                }
            }
        }
    }

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

7. Код на Python 3

import sys

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

    it = iter(data)
    n = int(next(it))
    is_connected = [[0] * n for _ in range(n)]
    for i in range(n):
        row = is_connected[i]
        for j in range(n):
            row[j] = int(next(it))

    used = [False] * n
    provinces = 0

    for start in range(n):
        if used[start]:
            continue

        provinces += 1
        stack = [start]
        used[start] = True

        while stack:
            u = stack.pop()
            row = is_connected[u]
            for v in range(n):
                if row[v] == 1 and not used[v]:
                    used[v] = True
                    stack.append(v)

    print(provinces)

if __name__ == "__main__":
    main()