Кварталы медного города

1. Идея

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

То есть для каждой компоненты надо понять:

• сколько в ней вершин;
• действительно ли каждая вершина соединена со всеми остальными вершинами этой компоненты.

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

Если в компоненте k вершин и она полная, то у каждой вершины степень внутри компоненты равна k - 1, а значит суммарная степень равна k * (k - 1).

Именно это и делает эталонное решение:

• находит каждую компоненту обходом в ширину;
• считает число её вершин vertices;
• считает сумму степеней всех вершин sum_deg;
• если sum_deg == vertices * (vertices - 1), то компонента полная.

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

Наблюдение 1. Квартал — это компонента связности

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

Значит задача сводится к перебору всех компонент графа.

Наблюдение 2. Полный граф на k вершинах

В полном графе:

• каждая вершина соединена со всеми остальными;
• у каждой вершины степень равна k - 1;
• сумма степеней равна k * (k - 1).

С другой стороны, в любой компоненте из k вершин максимальная возможная степень вершины не больше k - 1, поэтому суммарная степень не может быть больше k * (k - 1).

Если сумма степеней достигла этого максимума, значит каждая вершина имеет степень ровно k - 1, а значит компонента действительно полная.

Наблюдение 3. Одиночная вершина тоже считается

Если компонентa состоит из одной вершины, то:

• vertices = 1;
• sum_deg = 0;
• vertices * (vertices - 1) = 0.

Равенство выполняется, значит такая компонента считается завершённым кварталом. Это соответствует условию: внутри неё нет пары различных районов, для которой требовалась бы магистраль.

3. Алгоритм

1. Считываем n и m.
2. Строим список смежности графа.
3. Создаём массив used, чтобы отмечать уже посещённые вершины.
4. Для каждой вершины start:
   • если она уже посещена, пропускаем;
   • иначе запускаем BFS из start и обходим всю её компоненту.
5. Во время BFS:
   • считаем число вершин компоненты vertices;
   • прибавляем к sum_deg размер списка смежности текущей вершины.
6. После завершения обхода компоненты проверяем:
   • если sum_deg == vertices * (vertices - 1), увеличиваем ответ.
7. Выводим ответ.

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

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

Шаг 1. Обход действительно разбивает граф на компоненты связности

Запуская BFS из непосещённой вершины, мы посещаем:

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

Это ровно одна компонента связности. Так как после этого все её вершины помечены, повторно она не рассматривается. Значит каждая компонента будет обработана ровно один раз.

Шаг 2. Что считает sum_deg

Для найденной компоненты:

• vertices — количество её вершин;
• sum_deg — сумма степеней всех этих вершин в исходном графе.

Так как рёбер между разными компонентами нет, степень вершины внутри компоненты равна её степени в графе. Значит sum_deg — это именно сумма степеней внутри данной компоненты.

Шаг 3. Когда компонента является полной

Пусть в компоненте k = vertices вершин.

Если компонента полная, то каждая вершина соединена с k - 1 другими вершинами, поэтому sum_deg = k * (k - 1).

Теперь обратное. Если sum_deg = k * (k - 1), то это максимальная возможная сумма степеней для компоненты из k вершин, потому что степень каждой вершины не может превышать k - 1.

Значит каждая вершина обязана иметь степень ровно k - 1. Следовательно, каждая вершина соединена со всеми остальными, то есть компонента является полным графом.

Вывод

Алгоритм увеличивает ответ тогда и только тогда, когда найденная компонента является завершённым кварталом. Значит итоговый ответ верен.

5. Сложность

Пусть n — число вершин, m — число рёбер.

• Построение графа: O(m).
• Каждая вершина посещается один раз.
• Каждое ребро в списках смежности просматривается дважды.

Итоговая сложность: O(n + m).

Память:

• список смежности: O(n + m);
• массив посещения и очередь: O(n).

Итоговая память: O(n + m).

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        for (const auto& e : edges) {
            int u = e[0];
            int v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }

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

        for (int start = 0; start < n; ++start) {
            if (used[start]) continue;

            queue<int> q;
            q.push(start);
            used[start] = 1;

            long long vertices = 0;
            long long sum_deg = 0;

            while (!q.empty()) {
                int v = q.front();
                q.pop();

                ++vertices;
                sum_deg += (long long)g[v].size();

                for (int to : g[v]) {
                    if (!used[to]) {
                        used[to] = 1;
                        q.push(to);
                    }
                }
            }

            if (sum_deg == vertices * (vertices - 1)) {
                ++answer;
            }
        }

        return answer;
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(m, vector<int>(2));
    for (int i = 0; i < m; ++i) {
        cin >> edges[i][0] >> edges[i][1];
    }

    Solution sol;
    cout << sol.countCompleteComponents(n, edges) << '\n';
    return 0;
}

7. Код на Python 3

import sys
from collections import deque


class Solution:
    def countCompleteComponents(self, n, edges):
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        used = [False] * n
        answer = 0

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

            q = deque([start])
            used[start] = True

            vertices = 0
            sum_deg = 0

            while q:
                v = q.popleft()
                vertices += 1
                sum_deg += len(g[v])

                for to in g[v]:
                    if not used[to]:
                        used[to] = True
                        q.append(to)

            if sum_deg == vertices * (vertices - 1):
                answer += 1

        return answer


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

    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    edges = []
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        edges.append((u, v))

    sol = Solution()
    print(sol.countCompleteComponents(n, edges))


if __name__ == "__main__":
    main()