1. Идея

Дан неориентированный граф из n вершин и списка рёбер. Нужно посчитать, сколько его связных компонент являются полными графами.

Полная компонента размера k — это такая компонента, в которой каждая вершина соединена со всеми остальными вершинами этой же компоненты.
Значит, в ней должно быть ровно

[ \frac{k(k-1)}{2} ]

рёбер.

Задача сводится к двум шагам:

1. найти каждую связную компоненту;
2. проверить, является ли она полной.

Самая удобная идея: для каждой компоненты посчитать:

• сколько в ней вершин;
• сколько в ней рёбер.

Если число рёбер совпадает с формулой для полного графа, то компонента подходит.

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

Наблюдение 1. Полный граф определяется числом вершин и рёбер

Если связная компонента содержит k вершин, то:

• максимум рёбер внутри неё — это все пары вершин;
• число таких пар равно

[ \frac{k(k-1)}{2} ]

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

Наблюдение 2. Компоненты нужно рассматривать отдельно

Ребро между разными компонентами невозможно по определению связных компонент.
Поэтому можно независимо обрабатывать каждую компоненту.

Наблюдение 3. Изолированная вершина тоже образует полную компоненту

Если в компоненте всего одна вершина, то:

• k = 1;
• требуемое число рёбер:

[ \frac{1 \cdot 0}{2} = 0 ]

Это верно, значит одиночная вершина считается полной компонентой.

Наблюдение 4. Как удобно считать рёбра внутри компоненты

При обходе компоненты можно суммировать степени её вершин.

Если внутри компоненты E рёбер, то сумма степеней всех её вершин равна 2E, потому что каждое ребро учитывается дважды — по одному разу с каждого конца.

Значит:

[ E = \frac{\text{sumDegrees}}{2} ]

Это позволяет не хранить отдельно список рёбер компоненты.

3. Алгоритм

Будем хранить граф списком смежности.

Далее для каждой ещё не посещённой вершины запускаем обход в глубину (DFS) или в ширину (BFS), чтобы найти всю её связную компоненту.

Во время обхода компоненты считаем:

• vertices — число вершин в компоненте;
• degreeSum — сумму размеров списков смежности у этих вершин.

После завершения обхода:

• число рёбер в компоненте:

[ edges = \frac{degreeSum}{2} ]

• если

[ edges = \frac{vertices(vertices-1)}{2} ]

то увеличиваем ответ.

Пошагово

1. Построить список смежности по массиву edges.
2. Создать массив visited.
3. Для каждой вершины v от 0 до n-1:
   • если она ещё не посещена:
     • обойти всю её компоненту;
     • посчитать vertices и degreeSum;
     • вычислить realEdges = degreeSum / 2;
     • вычислить needEdges = vertices * (vertices - 1) / 2;
     • если realEdges == needEdges, прибавить 1 к ответу.
4. Вывести ответ.

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

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

Рассмотрим любую связную компоненту графа.

Пусть в ней k вершин.

1. Обход действительно находит ровно одну компоненту

DFS/BFS из некоторой непосещённой вершины посещает все вершины, достижимые из неё, и только их.
По определению это и есть её связная компонента.

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

2. Число рёбер компоненты считается правильно

Для каждой вершины мы прибавляем её степень в графе.
Так как рассматривается именно связная компонента, все рёбра её вершин ведут к вершинам той же компоненты.

Каждое ребро имеет два конца, поэтому в сумме степеней оно учтётся ровно два раза.
Следовательно,

[ \text{realEdges} = \frac{\text{degreeSum}}{2} ]

— это точное число рёбер в компоненте.

3. Условие полноты проверяется правильно

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

Число пар различных вершин равно

[ \frac{k(k-1)}{2} ]

Значит:

• если в компоненте ровно столько рёбер, то все пары соединены, и компонента полная;
• если рёбер меньше, то какой-то пары не хватает, и компонента не полная;
• больше быть не может в простом неориентированном графе.

Следовательно, проверка

[ \text{realEdges} = \frac{k(k-1)}{2} ]

эквивалентна тому, что компонента является полным графом.

4. Итог

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

5. Сложность

Пусть:

• n — число вершин;
• m — число рёбер.

Время

• Построение графа: O(m)
• Обход всех компонент: O(n + m)

Итого:

[ O(n + m) ]

Память

• список смежности: O(n + m)
• массив посещения: O(n)

Итого:

[ O(n + m) ]

CPP

#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], v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }

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

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

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

            long long vertices = 0;
            long long sumDegrees = 0;

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

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

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

            long long edgesInComponent = sumDegrees / 2;
            long long needEdges = vertices * (vertices - 1) / 2;

            if (edgesInComponent == needEdges) {
                ++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;
}

PYTHON

from collections import deque
import sys


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_degrees = 0

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

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

            edges_in_component = sum_degrees // 2
            need_edges = vertices * (vertices - 1) // 2

            if edges_in_component == need_edges:
                answer += 1

        return answer


def main():
    data = sys.stdin.read().strip().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()