Cod sursa(job #1563098)

Utilizator jurjstyleJurj Andrei jurjstyle Data 5 ianuarie 2016 18:02:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>

using namespace std ;

ifstream f ("dfs.in") ;
ofstream g ("dfs.out") ;

vector <int> G[100005] ;
bool vizitat[100005] ;
int N , M , nr ;

void citire () ;
void solve () ;
void dfs ( int ) ;

int main ()
{
 citire () ;
 solve () ;
 f.close () ;
 g.close () ;
 return 0 ;
}
void citire ()
{
 f >> N >> M ;
 for ( int i = 1 ; i <= M ; ++i )
    {
     int x , y ;
     f >> x >> y ;
     G[x].push_back ( y ) ;
     G[y].push_back ( x ) ;
    }
}
void solve ()
{
 for ( int i = 1 ; i <= N ; ++i )
    if ( !vizitat[i] )
        {
         ++nr ;
         dfs ( i ) ;
        }
 g << nr ;
}
void dfs ( int nod )
{
 vizitat[nod] = 1 ;
 for ( vector <int> :: iterator I = G[nod].begin() ; I < G[nod].end() ; ++I )
        if ( !vizitat[*I] )
            dfs ( *I ) ;
}