Cod sursa(job #2227896)

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

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

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

    scanf("%d %d", &nodes, &edges);

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

    for(int i = 1; i <= edges; i++)
    {
        scanf("%d %d", &u, &v);

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

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

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