Cod sursa(job #3377004)

Utilizator batasAndrei Batis batas Data 21 noiembrie 2026 08:40:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;

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

int n, m;
int timer;
VI low, disc;
VVI adj, scc;
VB inStk;
stack<int> stk;

void ReadInput();
void DFS(int node);
void ExtractSCC(int node);

int main()
{
    ReadInput();

    for (int node = 1; node <= n; ++node)
        if (disc[node] == -1)
            DFS(node);

    fout << scc.size() << '\n';

    for (auto curr : scc)
    {
        for (int node : curr)
            fout << node << ' ';
        fout << '\n';
    }

    return 0;
}

void DFS(int node)
{
    low[node] = disc[node] = ++timer;
    stk.push(node);
    inStk[node] = true;

    for (int nbr : adj[node])
        if (disc[nbr] == -1)
        {
            DFS(nbr);
            low[node] = min(low[node], low[nbr]);
        }
        else if (inStk[nbr])
            low[node] = min(low[node], disc[nbr]);

    if (low[node] == disc[node])
        ExtractSCC(node);
}

void ExtractSCC(int node)
{
    int next;
    VI curr;

    while (!stk.empty())
    {
        next = stk.top();
        stk.pop();
        inStk[next] = false;

        curr.push_back(next);

        if (next == node)
            break;
    }

    scc.push_back(curr);
}

void ReadInput()
{
    fin >> n >> m;

    low = disc = VI(n + 1, -1);
    inStk = VB(n + 1);
    adj = VVI(n + 1);

    int u, v;
    while (m--)
    {
        fin >> u >> v;

        adj[u].push_back(v);
    }
}