Cod sursa(job #1400889)

Utilizator TPotecTiberiu Potec TPotec Data 25 martie 2015 15:28:56
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
using namespace std;

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

int lst[100001],vf[200001],urm[200001], viz[100001];
int x,y,m=0,p,n,i,j,nr=0,v;

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

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

int main()
{
    in>>n>>v;
    for(i=1;i<=v;i++){
        in>>x>>y;
        adauga(x,y);
    }
    for(i=1;i<=n;i++){
        if(!viz[i]){
            nr++;
            dfs(i);
        }
    }
    out<<nr;
    return 0;
}