Cod sursa(job #1108214)

Utilizator felixiPuscasu Felix felixi Data 15 februarie 2014 15:00:43
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;

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

const int NMAX=100000;

bool viz[NMAX+1];

vector<int> d[NMAX+1];

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

int main()
{
    int sol=0, N,M, a,b;
    in>>N>>M;
    for(int i=0; i<M; i++){
        in>>a>>b;
        d[a].push_back(b);
        d[b].push_back(a);
    }
    for(int i=1; i<=N; i++){
        if( viz[ i ] == 0 ){
            viz[i]= 1;
            dfs( i );
            sol++;
        }

    }
    out<<sol<<'\n';
    in.close();
    out.close();
    return 0;
}