Cod sursa(job #2771185)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 25 august 2021 20:18:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
#include <list>
#include <iostream>

using namespace std;

int findNoSCC(list<int> *adj, const int N) {
    vector<bool> visited(N, false);
    vector<bool> isOnStack(N, false);

    vector<int> stack;

    int noSCC = 0;

    for (int v = 0; v < N; v++) {
        if (visited[v])
            continue;

        stack.push_back(v);
        isOnStack[v] = true;

        while (!stack.empty()) {
            int node = stack[stack.size() - 1];
            stack.pop_back();

            isOnStack[node] = false;

            for (const int &u : adj[node]) {
                if (!visited[u] && !isOnStack[u]) {
                    stack.push_back(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;

    list<int> adj[N];

    int x, y;

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

    int res = findNoSCC((list<int> *) adj, N);
    out << res;

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