Cod sursa(job #2860662)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 2 martie 2022 21:47:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

#define NMAX 100005
#define NEVIZITAT -1

int n, m, id[NMAX], low[NMAX], idcur, nrctc;
vector<int> G[NMAX], afis[NMAX];
stack<int> st;
bool in_stack[NMAX];

void citire() {
    f >> n >> m;
    int x, y;
    for (int i = 0; i < m; ++i) {
        f >> x >> y;
        G[x].push_back(y);
    }
}

void initializare() {
    for (int i = 1; i <= n; ++i)
        id[i] = NEVIZITAT;
}

void dfs(int x) {
    st.push(x);
    in_stack[x] = true;
    id[x] = low[x] = ++idcur;
    for (auto &nod: G[x]) {
        if (id[nod] == NEVIZITAT)
            dfs(nod);
        if (in_stack[nod])
            low[x] = min(low[x], low[nod]);
    }
    if (id[x] == low[x]) {
        nrctc++;
        int nod;
        do {
            nod = st.top();
            st.pop();
            in_stack[nod] = false;
            low[nod] = x;
            afis[nrctc].push_back(nod);
        } while (nod != x);
    }
}

void Tarjan() {
    for (int i = 1; i <= n; ++i)
        if (id[i] == NEVIZITAT) {
            dfs(i);
        }
}

void afisare() {
    g << nrctc << '\n';
    for (int i = 1; i <= nrctc; ++i) {
        for (auto &nod: afis[i])
            g << nod << ' ';
        g << '\n';
    }
}

int main() {
    citire();
    initializare();
    Tarjan();
    afisare();
}