Cod sursa(job #2795445)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 6 noiembrie 2021 13:07:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define VMAX 100000

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int V, E, x, y, timp, ctc;
vector <int> adj[VMAX];
vector <int> comp[VMAX];
stack <int> st;
bool onStack[VMAX];
int disc[VMAX], low[VMAX];

void Tarjan(int u)
{
    disc[u] = low[u] = ++timp;
    st.push(u);
    onStack[u] = true;

    for (auto w:adj[u]) {
        if (!disc[w]) {
            Tarjan(w);
            low[u] = min(low[u], low[w]);
        }
        else if (onStack[w]) low[u] = min(low[u], disc[w]); // !
    }

    if (low[u] == disc[u]) {
        while (st.top() != u) {
            x = st.top();
            comp[ctc].push_back(x + 1);
            onStack[x] = false;
            st.pop();
        }
        x = st.top();
        comp[ctc].push_back(x + 1);
        onStack[x] = false;
        st.pop();
        ++ctc;
    }
}
int main()
{
    fin >> V >> E;

    while (E--) {
        fin >> x >> y;
        adj[x - 1].push_back(y - 1);
    }

    for (int i = 0; i < V; ++i)
        if (!disc[i]) Tarjan(i);

    fout << ctc << '\n';

    for (int i = 0; i < ctc; ++i) {
        for (auto elem:comp[i]) fout << elem << " ";
        fout << '\n';
    }
}