Cod sursa(job #2134142)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 17 februarie 2018 17:55:42
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#define NMAX (100000 + 3)
#define MMAX (1000000 + 3)
using namespace std;


void DFS(int n, int source, vector<int> neighbors[], bool visited[]) {
    stack<int> stack;
    stack.push(source);

    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();

        for (auto const &ngbr : neighbors[node]) {
            if (!visited[ngbr]) {
                visited[ngbr] = true;
                stack.push(ngbr);
            }
        }
    }

}

int main() {

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

    vector<int> neighbors[NMAX];
    bool visited[NMAX];

    int n, m, i, j, source;

    f >> n >> m;

    for (; m; --m) {
        int x, y;
        f >> x >> y;
        neighbors[x].push_back(y);
    }

    int connected_comp = 0;

    for (i = 1; i <= n; ++i) {
        visited[i] = false;
    }

    for (i = 1; i <= n; ++i) {
        if (!visited[i]) {
            ++connected_comp;
            DFS(n, i, neighbors, visited);
        }
    }

    g << connected_comp;

    return 0;
}