Cod sursa(job #2771343)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 26 august 2021 19:05:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <fstream>
#include <vector>
#include <list>

using namespace std;

#define NL "\n"
#define SPACE " "

enum color {
    WHITE, GRAY, BLACK
};

void tarjan(list<int> *adj, const int N, int u, vector<int> &d,
        vector<int> &low, vector<enum color> &c, list<int> &stack,
        vector<bool> &isOnStack, int &time, list<list<int>> &SCC);

void findSCC(list<int> *adj, const int N, ofstream &out) {
    // timpii de descoperire a fiecarui nod
    vector<int> d(N, 0);
    vector<enum color> c(N, WHITE);
    // cel mai devreme descoperit stramos accesibil folosind o singura muchie
    // inapoi sau incrucisata, plecand din nodul curent in arborele DFS
    vector<int> low(N, 0);

    list<int> stack;
    vector<bool> isOnStack(N, false);
    list<list<int>> SCC;

    int time = 0;

    for (int u = 0; u < N; u++) {
        if (c[u] == WHITE) {
            tarjan((list<int> *) adj, N, u, d, low, c, stack, isOnStack, time,
                SCC);
        }
    }

    out << SCC.size() << NL;

    while (!SCC.empty()) {
        list<int> scc = SCC.front();
        SCC.pop_front();

        while (!scc.empty()) {
            int u = scc.front();
            scc.pop_front();

            out << ++u << SPACE;
        }
        out << NL;
    }
}

void tarjan(list<int> *adj, const int N, int u, vector<int> &d,
        vector<int> &low, vector<enum color> &c, list<int> &stack,
        vector<bool> &isOnStack, int &time, list<list<int>> &SCC) {
    d[u] = low[u] = time++;
    c[u] = GRAY;

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

    for (int v : adj[u]) {
        if (c[v] == WHITE) {
            tarjan(adj, N, v, d, low, c, stack, isOnStack, time, SCC);
            low[u] = min(low[u], low[v]);
        } else if (isOnStack[v]) {
            low[u] = min(low[u], d[v]);
        }
    }

    if (low[u] == d[u]) {
        list<int> newScc;

        while (true) {
            int w = stack.back();
            stack.pop_back();
            isOnStack[w] = false;

            newScc.push_front(w);
            if (w == u) {
                break;
            }
        }

        SCC.push_back(newScc);
    }
}

int main(void) {
    const string INPUT_FILENAME = "ctc.in";
    const string OUTPUT_FILENAME = "ctc.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);
    }

    findSCC((list<int> *) adj, N, out);

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