Cod sursa(job #3314745)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 10 octombrie 2025 22:56:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <cstdio>
#include <vector>

using graph = std ::vector<std ::vector<int>>;

namespace InParser
{
    static constexpr int BSIZE = (1 << 16);

    static int pos = (BSIZE - 1);
    static char buff[BSIZE];

    char get_char()
    {
        ++pos;
        if (pos == BSIZE)
        {
            pos = 0;
            int n = fread(buff, 1, BSIZE, stdin);

            if (n != BSIZE)
                for (int i = n; i < BSIZE; ++i)
                    buff[i] = 0;
        }

        return buff[pos];
    }

    unsigned int get_unsigned_int()
    {
        unsigned int answer = 0;
        for (;;)
        {
            char ch = get_char();
            if ((ch >= '0') && (ch <= '9'))
            {
                answer = (unsigned int)(ch - '0');
                break;
            }
        }

        for (;;)
        {
            char ch = get_char();
            if ((ch >= '0') && (ch <= '9'))
                answer = (answer * 10) + (unsigned int)(ch - '0');
            else
                break;
        }

        return answer;
    }
};

void dfs(const graph &G, std ::vector<bool> &used, const int node = 1)
{
    used[node] = true;
    for (const int &adj : G[node])
        if (!used[adj])
            dfs(G, used, adj);

    return;
}

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

    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    unsigned int n = InParser ::get_unsigned_int(), m = InParser ::get_unsigned_int();
    graph G((n + 1));

    for (unsigned int i = 0; i < m; ++i)
    {
        unsigned int x = InParser ::get_unsigned_int(),
                     y = InParser ::get_unsigned_int();

        G[x].push_back(y),
            G[y].push_back(x);
    }

    std ::vector<bool> used((n + 1), false);

    unsigned int answer = 0;

    for (unsigned int node = 1; node <= n; ++node)
        if (!used[node])
            ++answer,
                dfs(G, used, node);

    printf("%d\n", answer);

    return 0;
}