Cod sursa(job #1001114)

Utilizator alexx.cosmaCosma Cristian Alexandru alexx.cosma Data 24 septembrie 2013 15:31:19
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int N,M;

const int maxN = 100010;

vector<int>adj[maxN];

int vis[maxN];

void dfs();
void dfs(int i);
int main()
{
    fin>>N;
    fin>>M;
    for(int i=0; i<M; i++)
    {
        int source,dest;
        fin>>source;
        fin>>dest;
        adj[source].push_back(dest);
    }
    dfs();
    return 0;
}

void dfs()
{
    stack<int> st;
    int nrConexe =0;
    for(int i=0; i<N; i++)
    {
        if(vis[i]==0)
        {
            nrConexe++;
            dfs(i);
        }
    }

    fout<<nrConexe;
    fout<<endl;
}

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