Cod sursa(job #3336573)

Utilizator RalucaioneteRalucaIonete Ralucaionete Data 24 ianuarie 2026 22:07:23
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int N = 1e5;
vector<int> lista_ad[N + 1], transpus[N + 1], ctc[N + 1];
stack<int> ordine; // timpi iesire
bool vizitat[N + 1];
int nr_ctc = 1;

void dfs(int start)
{
    for (int j : lista_ad[start])
    {
        if (!vizitat[j])
        {
            vizitat[j] = true;
            dfs(j);
            ordine.push(start);
        }
    }
}

void dfs_transpus(int start_t, int nr_ctc)
{
    for (int j : transpus[start_t])
    {
        if (!vizitat[j])
        {
            vizitat[j] = true;
            dfs_transpus(j, nr_ctc);
            ctc[nr_ctc].push_back(j);
        }
    }
}

int main()
{
    int n, m;
    in >> n >> m;

    int u, v;
    for (int i = 0; i < m; i++)
    {
        in >> u >> v;
        lista_ad[u].push_back(v);
        transpus[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        vizitat[i] = false;

    vizitat[1] = true;
    dfs(1);

    for (int i = 2; i <= n; i++)
    {
        if (!vizitat[i])
            dfs(i);
    }

    // acum am efectuat prima parcurgere DFS pe graful original G si am obtinut ordinea nodurilor
    // in functie de timpii de iesire

    for (int i = 1; i <= n; i++)
        vizitat[i] = false;

    while (!ordine.empty())
    {
        int start_transpus = ordine.top();
        ordine.pop();

        if (!vizitat[start_transpus])
        {
            vizitat[start_transpus] = true;
            ctc[nr_ctc].push_back(start_transpus);
            dfs_transpus(start_transpus, nr_ctc);
            nr_ctc++;
        }
    }

    out << nr_ctc - 1 << '\n';
    for (int i = 1; i < nr_ctc; i++)
    {
        for (size_t j = 0; j < ctc[i].size(); j++)
            out << ctc[i][j] << " ";
        if(i != nr_ctc - 1)
            out << '\n';
    }
    return 0;
}