Cod sursa(job #1872784)

Utilizator dragosmdvMoldovan Dragos dragosmdv Data 8 februarie 2017 16:29:06
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

queue <int> q;
vector <int> v[100002];

int i, n, m, a, cont, b, freq[100002];

void dfs(int nod)
{
    freq[nod]=1;
    for(int i=0;i<v[nod].size();i++)
    {
        if(freq[v[nod][i]]!=1)
            dfs(v[nod][i]);
    }


}




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(freq[i]!=1)
        {
            dfs(i);
            cont++;
        }

    }
    fout<<cont;


    return 0;
}