Cod sursa(job #1936398)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 23 martie 2017 07:01:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <vector>
#define NMAX 100005
#include <stack>
using std::stack;
using std::vector;

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

int main(){

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

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

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

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

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

    return 0;
}