Cod sursa(job #3123269)

Utilizator adaxndDobrica Nicoleta Adriana adaxnd Data 22 aprilie 2023 19:16:54
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 200000

using namespace std;

vector<vector<int> > ctc;
vector<int> ctc_aux;


void tarjan(int node, vector<int> adj[NMAX], vector<int> &nodeIndex, vector<int> &lowlink,
            vector<int> &onStack, stack<int> &st, int &index) {

    nodeIndex[node] = lowlink[node] = ++index;
    st.push(node);
    onStack[node] = true;

    for (int i = 0; i < adj[node].size(); i++) {
        int v = adj[node][i];

        if (nodeIndex[v] == -1) {
            tarjan(v, adj, nodeIndex, lowlink, onStack, st, index);
            lowlink[node] = min(lowlink[node], lowlink[v]);
        } else if (onStack[v] == true) {
            lowlink[node] = min(lowlink[node], nodeIndex[v]);
        }
    }

    int w = 0;
    if (lowlink[node] == nodeIndex[node]) {
        ctc_aux.clear();

       do {
            w = st.top();
            ctc_aux.push_back(w);
            st.pop();
            onStack[w] = false;
        } while (w != node);

        ctc.push_back(ctc_aux);
    }
}

void find_ctc(int n, vector<int> adj[NMAX]) {
    vector<int> nodeIndex(n + 1, -1);
    vector<int> lowlink(n + 1, -1);
    vector<int> onStack(n + 1, false);
    stack<int> st;

    int index = 0;

    for (int i = 1; i <= n; i++) {
        if (nodeIndex[i] == -1) {
            tarjan(i, adj, nodeIndex, lowlink, onStack, st, index);
        }
    }
}

void print_ctc() {
    ofstream fout("ctc.out");

    fout << ctc.size() << "\n";

    for (int i = ctc.size() - 1; i >= 0; i--) {
        for (int j = ctc[i].size() - 1; j >= 0; j--) {
            fout << ctc[i][j] << " ";
        }
        fout << "\n";
    }
}


int main() {
    ifstream fin("ctc.in");

    int n, m;
    fin >> n >> m;

    vector<int> adj[n + 1];
    
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
    }

    find_ctc(n, adj);
    print_ctc();

    return 0;

}