Cod sursa(job #1187273)

Utilizator alevasluialeHuhurez Marius alevasluiale Data 18 mai 2014 01:12:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector <int> v[500001];
bitset <100001> viz;
inline void dfs(int x,bool &ok)
{
    viz[x]=1;
    for(vector <int>::iterator it=v[x].begin();it!=v[x].end();it++)
    {
        if(viz[*it]==0)
        {
            dfs(*it,ok);
            ok=true;
        }
    }
}
int main()
{
    int n,m,i,x,y;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }
    i=1;
    bool ok=true;
    while(ok!=false)
    {   x=1;
        ok=false;
        while(viz[x]) x++;
        dfs(x,ok);
        i++;
    }
    fout<<i-1;
}