Cod sursa(job #2227904)

Utilizator inquisitorAnders inquisitor Data 2 august 2018 10:24:23
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 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], rank[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)
        {
            if(rank[u] > rank[v]) parent[v] = u;

            else parent[u] = v;

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