Cod sursa(job #1142269)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 13 martie 2014 17:47:37
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<vector>

using namespace std;

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

const int nmax = 100000;
bool v[nmax+1];
vector <int> g[nmax+1];

void dfs( int nod ) {
    v[nod] = 1;
    for( int i = 0; i < (int)g[nod].size(); ++ i ) {
        if ( v[ g[nod][i] ] == 0 )
            dfs( g[nod][i] );
    }

}
int main()
{
    int n, m, a, b, sol;
    fin>>n>>m;
    sol = 0;
    for( int i = 0; i < m; ++ i ) {
        fin>>a>>b;
        g[a].push_back( b );
        g[b].push_back( a );
    }
    for ( int i = 1; i <= n; ++ i ) {
        if ( v[i] == 0 ) {
            dfs( i );
            ++sol;
        }
    }
    fout<<sol<<'\n';
    fin.close();
    fout.close();
    return 0;
}