Cod sursa(job #2227892)

Utilizator inquisitorAnders inquisitor Data 2 august 2018 10:11:24
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>

int v[100001];

__attribute__((always_inline)) int Find(int x)
{
    int aux;

    while(x != v[x])
    {
        aux = v[v[x]],

        v[x] = aux,

        x = aux;
    }

    return x;
}

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

    int n, m, x, y, nr = 0;

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; ++i)
    {
        v[i] = i;
    }

    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d", &x, &y);

        if(Find(x) != Find(y)) ++nr; v[x] = y;
    }
    printf("%d\n" ,n - nr);
}