Cod sursa(job #1087335)

Utilizator varga13VarGaz13 varga13 Data 19 ianuarie 2014 11:58:07
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
#define mx 10000
using namespace std;

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

int n, m,k ;
bool sol[mx];
vector<int> nods[mx];

void read()
{
    f>>n>>m;
    for(int i=0;i<m;++i)
    {
        int aux1, aux2;
        f>>aux1>>aux2;
        nods[aux1].push_back(aux2);
    }
}

void Dfs(int nod)
{
    if(sol[nod]) return;

    sol[nod]=1;
    for(int i=0;i<nods[nod].size();++i)
    {
        Dfs(nods[nod][i]);
    }
}

int main()
{
    read();
    for(int i=0;i<n;i++)
    {
        if(!sol[i])
            k++,Dfs(i);
    }
    g<<k;
    f.close();
    g.close();
    return 0;
}