Cod sursa(job #1546988)

Utilizator andrei_bB. Andrei andrei_b Data 8 decembrie 2015 21:39:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> v[100005];
int n,cate,a,b;
long long m;
bool da[100005];

void dfs ( int p ){

    if ( da[p] )
        return;

    da[p] = true;

    for ( int i=0 ; i<v[p].size() ; i++ ){
        if ( !da[v[p][i]] )
            dfs(v[p][i]);
    }


}


int main()
{
    fin>>n>>m;
    for ( long long i=1 ; i<=m ; i++ ){
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for ( int i=1 ; i<=n ; i++ ){
        if ( !da[i] ){
            dfs(i);
            cate++;
        }
    }
    fout<<cate;
}