Cod sursa(job #1217122)

Utilizator andreimdvMoldovan Andrei andreimdv Data 6 august 2014 17:11:47
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
#include<vector>
#include<list>
using namespace std;


ifstream fin("dfs.in");
ofstream fout("dfs.out");
int i,n,m,a,b,con,vizitat[100010];
vector<list<int> > v(100010);

void conex(int nod)
{
    list <int> :: iterator it;
    vizitat[nod]=con;
    for(it=v[nod].begin();it!=v[nod].end();it++)
    {
        if(vizitat[*it]==0)
        conex(*it);
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b;
        v[a].push_back(b);
    }
    for(i=1;i<=n;++i)
    {
        if(vizitat[i]==0)
        {
            con++;
            conex(i);
        }
    }
    fout<<con;
    return 0;
}