Cod sursa(job #1936391)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 23 martie 2017 06:46:42
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>
#define NMAX 100005
#include <stack>
using std::stack;
using std::vector;

void DFS(int node, bool viz[], vector <int> G[], stack <int> S){
    viz[node] = true;
    S.push(node);
    while(!S.empty()){
        node = S.top();
        S.pop();
        for(int i{0};i < G[node].size();++i){
            if(!viz[G[node][i]]){
                viz[G[node][i]] = true;
                S.push(G[node][i]);
            }
        }
    }
}

int main(){

    freopen("dfs.in","r", stdin);
    freopen("dfs.out", "w",stdout);

    int N, M;
    std::vector <int> G[NMAX];
    stack <int> S;
    int x,y;
    bool viz[NMAX];

    scanf("%d %d ", &N, &M);
    while(M--){
        scanf("%d %d ", &x, &y);
        G[x].push_back(y);
    }

    int nrc{0};

    for(int i{1};i <= N;i++)
        if(!viz[i]){
            DFS(i, viz, G, S);
            nrc++;
        }

    printf("%d\n", nrc);

    return 0;
}