Cod sursa(job #3340871)

Utilizator dragutamihai1234Draguta Mihai dragutamihai1234 Data 16 februarie 2026 21:02:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 1e5 + 1;

vector<int> G[NMAX], GT[NMAX], ctc[NMAX];
vector<int> order;
bool viz[NMAX];
int nr = 0;
int n, m;
void read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        f >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
}

void order_dfs(int node)
{
    viz[node] = true;
    for (int to : G[node])
        if (!viz[to])
            order_dfs(to);
    order.push_back(node);
}

void CTC_dfs(int node)
{
    viz[node] = true;
    ctc[nr].push_back(node);
    for (int to : GT[node])
        if (!viz[to])
            CTC_dfs(to);
}

void dfs_driver_order()
{
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            order_dfs(i);
}

void dfs_driver_CTC()
{
    for (int i = 1; i <= n; i++)
        viz[i] = 0;
    for (int x = n - 1; x >= 0; x--)
    {
        int i = order[x];
        if (!viz[i])
        {
            nr++;
            CTC_dfs(i);
        }
    }
}
void afis()
{
    g << nr << '\n';
    for (int i = 1; i <= nr; i++)
    {
        for (int x : ctc[i])
            g << x << ' ';
        g << '\n';
    }
}
int main()
{
    read();
    dfs_driver_order();
    dfs_driver_CTC();
    afis();
    return 0;
}