Cod sursa(job #839480)

Utilizator mvcl3Marian Iacob mvcl3 Data 21 decembrie 2012 21:12:30
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
#include<vector>
#include<queue>
#define NMAX 100009
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int n, m, nod_a, nod_b, viz[NMAX];
queue<int>q;
vector<int>x[NMAX];
inline void citire();
inline void dfs(int);
int main()
{
    citire();
    int nr_cp = 0;
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
        {
            nr_cp++;
            dfs(i);
        }
    g<<nr_cp<<'\n';
    g.close();
    return 0;
}
inline void citire()
{
    f>>n>>m;
    for(int i = 1; i <= m; ++i)
    {
        f>>nod_a>>nod_b;
        x[nod_a].push_back(nod_b);
    }
    f.close();
}
inline void dfs(int k)
{
    q.push(k);
    viz[k] = 1;
    while(!q.empty())
    {
        k = q.front(); q.pop();
        vector<int>::iterator it;
        for(it = x[k].begin(); it != x[k].end(); ++it)
            if(!viz[(*it)])
            {
                viz[(*it)] = 1;
                q.push((*it));
            }
    }
}