Cod sursa(job #2781275)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 8 octombrie 2021 21:45:38
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <bits/stdc++.h>
#include <fstream>
#define VMAX 100000

using namespace std;

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

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

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

    for (auto w:adj[u])
    {
        if (!disc[w]) // elem. nou gasit, (u, v) tree edge
        {
            Tarjan(w);
            // daca componenta aferenta lui v e mai "proaspata", atunci pot sa il bag si pe u in ea, ptc (u, v) e muchie deci pot accesa ac. ctc
            low[u] = min(low[u], low[w]);
        }
        else if (onStack[w]) // daca este pe stack, atunci este unul dintre descendentii lui u
            low[u] = min(low[u], disc[w]); // (ex geeksforgeeks) exista cazul in care w este "nodul de trecere" dintre o ctc si alta, deci low[w] ar indica eronat alta comp. conexa
        else continue; // altfel, (u, v), este cross edge spre un CTC deja analizat, deci nu facem nimic
    }

    if (low[u] == disc[u]) // reprez. head node intr un SCC, adica nodul din SCC cu cel mai mic discovery time
    {
        while (s.top() != u) // cat timp nu ajung la head node
        {
            x = s.top();
            ctc[nr_ctc].push_back(x);
            onStack[x] = false;
            s.pop();
        }
        x = s.top();
        ctc[nr_ctc].push_back(x);
        onStack[x] = false;
        s.pop();
        ++nr_ctc;
    }
}

int main()
{
    fin >> V >> E;

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

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

    fout << nr_ctc << endl;

    for (int i = 0; i < nr_ctc; ++i)
    {
        for (int j = 0; j < ctc[i].size(); ++j)
            fout << ctc[i][j] + 1 << " ";
        fout << endl;
    }

    fin.close();
    fout.close();
    return 0;
}