Cod sursa(job #1456648)

Utilizator petru.cehanCehan Petru petru.cehan Data 1 iulie 2015 15:26:19
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("dfs.in") ;
ofstream fout ("dfs.out") ;

struct nod
{
    nod * next ;
    int info ;
} ;

nod * L [100001] ;
int viz [100001] , N , M ;

void Add ( int , int ) ;
void Citire ()
{
    int a , b ;
    fin >> N >> M ;
    while ( M >= 1 )
    {
        fin >> a >> b ;
        Add ( a , b ) ;
        -- M ;
    }
}

void Add ( int a , int b )
{
    nod * p = new nod ;
    p->info = b ;
    p->next = L [a] ;
    L [a] = p ;
}

void DFS ( int nd )
{
    nod * p ;
    viz [nd] = 1 ;
    for ( p = L [nd] ; p != 0 ; p = p->next )
          if ( viz [ p->info ] == 0 )
                DFS ( p->info ) ;
}

int main()
{
    Citire () ;
    int nr = 0 , i ;
    for ( i = 1 ; i <= N ; ++ i )
          if ( viz [i] == 0 )
              ++ nr ,  DFS (i) ;

    fout << nr ;
    return 0;
}