Cod sursa(job #2771180)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 25 august 2021 19:25:46
Problema Parcurgere DFS - componente conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

int findNoSCC(unordered_map<int, unordered_set<int>> &adj) {
    vector<bool> visited(adj.size(), false);
    vector<bool> isOnStack(adj.size(), false);

    stack<int> nodes;

    int noSCC = 0;

    for (auto &nodeAdj : adj) {
        int w = nodeAdj.first;

        if (visited[w])
            continue;

        nodes.push(w);
        isOnStack[w] = true;

        while (!nodes.empty()) {
            int node = nodes.top();
            nodes.pop();
            isOnStack[node] = false;

            for (const int &u : adj[node]) {
                if (!visited[u] && !isOnStack[u]) {
                    nodes.push(u);
                    isOnStack[u] = true;
                }
            }
            visited[node] = true;
        }
        noSCC++;
    }

    return noSCC;
}

int main(void) {
    const string INPUT_FILENAME = "dfs.in";
    const string OUTPUT_FILENAME = "dfs.out";

    ifstream in(INPUT_FILENAME);
    ofstream out(OUTPUT_FILENAME);

    int N, M, i;
    in >> N >> M;

    unordered_map<int, unordered_set<int>> adj;
    adj.reserve(N);
    for (int i = 0; i < N; i++)
        adj[i] = {};

    int x, y;

    for (i = 0; i < M; i++) {
        in >> x >> y;
        --x;
        --y;
        adj[x].insert(y);
        adj[y].insert(x);
    }

    int res = findNoSCC(adj);
    out << res;

    in.close();
    out.close();
    return 0;
}