Cod sursa(job #2227902)

Utilizator inquisitorAnders inquisitor Data 2 august 2018 10:21:06
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>

char buffer[2000000]; int p = -1;

__attribute__((always_inline)) int get_int()
{
    int number = 0;

    for(++p; buffer[p] > 47; ++p)
    {
        number = number * 10 + buffer[p] - 48;
    }

    return number;
}

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

    fread(buffer, 1, 2000000, stdin);

    int nodes, edges, parent[100001], u, v, t, x = 0;

    nodes = get_int();

    edges = get_int();

    for(int i = 1; i <= nodes; i++)
    {
        parent[i] = i;
    }

    for(int i = 1; i <= edges; i++)
    {
        u = get_int();

        v = get_int();

        while(u != parent[u]) u = parent[u];

        while(v != parent[v]) v = parent[v];

        if(u != v) x++; parent[u] = v;
    }
    printf("%d", nodes - x);
}