Cod sursa(job #2196530)

Utilizator cristiancreteanuCristian Creteanu cristiancreteanu Data 19 aprilie 2018 17:50:02
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

void DFS(int src, vector<vector<int>>& adj, vector<bool>& visited) {
    stack<int> dfs;
    int node;

    dfs.push(src);
    visited[src] = true;

    while (!dfs.empty()) {
        node = dfs.top();

        for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
            if (!visited[*it]) {
                visited[*it] = true;
                dfs.push(*it);
                continue;
            }
        }

        dfs.pop();
    }
}

int main() {
    int x, y, N, M, i, conex;

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

    f >> N >> M;

//    vector<int> grd(N + 1, 0)
    vector<vector<int>> adj(N + 1);
    vector<bool> visited(N + 1, false);
    for (i = 1; i <= M; ++i) {
        f >> x >> y;

        adj[x].push_back(y);
//        grd[y]++;
    }

    conex = 0;
    for (i = 1; i <= N; ++i) {
        if (!visited[i]) {
            DFS(i, adj, visited);
            ++conex;
        }
    }

    g << conex << '\n';

    g.close();
    f.close();

    return 0;
}