Cod sursa(job #1427462)

Utilizator xtreme77Patrick Sava xtreme77 Data 2 mai 2015 12:27:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>

using namespace std;

const int MAX = 100014 ;

vector < int > gr [ MAX ] ;

int viz [ MAX ] ;

inline void dfs ( int nod )
{
    viz [ nod ] = 1 ;
    for ( auto x : gr [ nod ] )
        if ( viz [ x ] == 0 )
            dfs ( x ) ;
}

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

int main ( void )
{
    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= m ; ++ i )
    {
        int x , y ;
        fin >> x >> y ;
        gr [ x ].push_back ( y ) ;
        gr [ y ].push_back ( x ) ;
    }
    int comp = 0 ;
    for ( int i = 1 ; i <= n ; ++ i )
        if ( viz [ i ] == 0 )
        {
            ++ comp ;
            dfs ( i ) ;
        }
    fout << comp << '\n' ;
    return 0;
}