DFS

#include <iostream>
#include <vector>

using namespace std;

int dfs(const vector<vector<bool>>& g, vector <bool>& used, int v)//передаем в параметры сам граф (матрицу смежности), вектор посещённых вершин и саму вершину
{
    int cnt = 0;//счётчик для подсчёта кол-ва вершин, в которые мы можем попасть из вершины v
    if (used[v])//если мы уже были в этой вершине, то не считаем её
        return -1;//возвращаем -1
    used[v] = true;//помечаем вершину v, что мы её посещали
    for (size_t i = 0; i < g.size(); ++i)//пробегаемся по всем вершинам, чтобы найти, пометить и посчитать те, в которые мы можем попасть
    {
        if (g[v][i] && !used[i])//проверяем, есть ли путь из v в i, и не были ли мы уже в i
        {
            ++cnt;//считаем такую вершину
            cnt += dfs(g, used, i);//и запускаемся дальше, для подсчёта всех вершин, в которые мы можем попасть из i-той
        }

    }
    return cnt; //вовзвращаем такое кол-во
}

int main()
{
    int n, e; //n - количество вершин в графе, e - количество рёбер
    cin >> n >> e;
    vector<vector <bool>> g(n, vector <bool>(n, false)); //Матрица смежности для хранения графа размером NxN, изначально заполнена нулями
    vector <bool> used (n, 0); //вектор, в котором мы помечаем посещённые вершины
    for (int i = 0; i < e; ++i) //здесь мы заполняем нашу матрицу смежности
    {
        int a, b;
        cin >> a >> b; //считываем вершины, между котороыми есть ребро
        a--;//отнимаем по еденице, так как индексы с нуля
        b--;//тут тоже самое
        g[a][b] = 1;//Ставим единичку, чтобы показать, что из "а" есть путь в "b"
        g[b][a] = 1;//Тоже самое, но наоборот
    }

    int ans(0);//Счётчик для подсчёта компонентов
    vector <int> components;//вектор для хранения размеров компонент
    for (int i = 0; i < n; ++i)//бежим по всем вершинам
    {
        int k = dfs(g, used, i);//запускаемся от первой вершины и считаем во сколько вершин мы можем попасть из неё. (описание dfs выше)
        if (k >= 0)//если кол-во вершин, в которые мы можем попасть из i-той вершины больше равно нуля, то это очередной компонент графа
        {
            ++ans;//считаем кол-во компонентов
            components.push_back(k + 1);//добавляем размер этого компонента (+1 делается для того, чтобы добавить саму стартовую вершину
        }
    }
    cout << "Amount of components: " << ans << ": \n"; //стандартный вывод
    for (const auto& i : components)
        cout << i << ' ';

    return 0;
}
//Дальше примеры
//Пример 1: ответ должен быть 3 => [3 2 5]
/*
10 7
1 2
1 3
4 5
6 7
7 8
7 9
7 10
*/
//Пример 2: ответ должен быть 3 => [1 1 1]
/*
3 0
*/

//Пример 3: ответ должен быть 2 => [3, 2]
/*
5 4
1 2
2 3
3 1
4 5
*/