Cod sursa(job #2227890)

Utilizator inquisitorAnders inquisitor Data 2 august 2018 10:08:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <cstdio>

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

    int n, m, v[100001], x, y, aux, 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);

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

        while(y != v[y]) aux = v[v[y]], v[y] = aux, y = aux;

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