Cod sursa(job #146707)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 2 martie 2008 00:16:36
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

struct point { int v ; point *l; } *G[100000];
int U[100001],n,m;

void Df ( int x )
{
    U[x]=1;
    point *p;
    for ( p = G[x] ; p ; p = p -> l )
        if (!U[p->v]) Df ( p->v );
}

int main ()
{
    point *p;
    int x,y,i,r=0;
    freopen ( "dfs.in" , "r" , stdin );
    scanf ( "%d %d" , &n , &m );
    for ( i=0 ; i<m ; i++ )
    {
        scanf ( "%d %d" , &x , &y );
        p = new point;
        p->v = y;
        p->l = G[x];
        G[x] = p;
        p = new point;
        p->v = x;
        p->l = G[y];
        G[y] = p;
    }
    fclose ( stdin );

    for ( i=1 ; i<=n ; i++ )
        if (!U[x])
        {
            r++;
            Df(x);
        }

    freopen ( "dfs.out" , "w" , stdout );
    printf ( "%d\n" , r );
    fclose ( stdout );

    return 0;
}