Cod sursa(job #1627383)

Utilizator andrei_bB. Andrei andrei_b Data 3 martie 2016 16:59:08
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>

using namespace std;

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

const int Nmax=100005;
const int Mmax=200005;

int n,m,a,b,nr,vf[Mmax],lst[Nmax],urm[Mmax],cate;
bool da[Nmax];

void adauga ( int x , int y ){
    nr++;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}

void dfs ( int x ){
    int y,p;
    p=lst[x];
    while ( p != 0 ) {
        y=vf[p];
        da[y]=true;
        p=urm[p];
    }
}

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