Cod sursa(job #3314748)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 10 octombrie 2025 23:25:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <iostream>
#include <cstdio>

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(unsigned int *N, unsigned int *F, bool *used, const int node = 1)
{
    used[node] = true;
    for (unsigned int i = N[node]; i < N[(node + 1)]; ++i)
        if (!used[F[i]])
            dfs(N, F, used, F[i]);

    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();

    unsigned int *N = (unsigned int *)calloc((n + 2), sizeof(unsigned int));
    unsigned int *F = (unsigned int *)malloc((m << 1) * sizeof(unsigned int));
    std ::pair<int, int> *edges = (std ::pair<int, int> *)malloc(m * sizeof(std ::pair<int, int>));

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

        ++N[x], ++N[y];
        edges[i] = {x, y};
    }

    for (unsigned int i = 2; i <= (n + 1); ++i)
        N[i] += N[(i - 1)];

    for (unsigned int i = 0; i < m; ++i)
    {
        unsigned int x = edges[i].first, y = edges[i].second;
        F[--N[x]] = y, F[--N[y]] = x;
    }
    bool *used = (bool *)calloc((n + 1), sizeof(bool));

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

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

    if (N)
        free(N);
    if (F)
        free(F);
    if (edges)
        free(edges);
    if (used)
        free(used);

    return 0;
}