Cod sursa(job #1694590)

Utilizator xtreme77Patrick Sava xtreme77 Data 25 aprilie 2016 17:12:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include <bits/stdc++.h>

const char IN [ ] =  "dfs.in" ;
const char OUT [ ] = "dfs.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

const int MAX = 1e5 + 14 ;

vector < int > gr [ MAX ] ;
bool vizitat [ MAX ] ;

void dfs ( int nod ) {
    vizitat [ nod ] = 1 ;
    for ( auto vecin : gr [ nod ] ) {
        if ( ! vizitat [ vecin ] ) {
            dfs ( vecin ) ;
        }
    }
}

int main()
{
    int n , m ;
    fin >> n >> m ;
    while ( m -- ) {
        int a , b ;
        fin >> a >> b ;
        gr [ a ].pb ( b ) ;
        gr [ b ].pb ( a ) ;
    }
    int comp = 0 ;
    FORN ( i , 1 , n ) {
        if ( vizitat [ i ] == 0 ) {
            ++ comp ;
            dfs ( i ) ;
        }
    }
    fout << comp << '\n' ;
    return 0;
}