Cod sursa(job #3287033)

Utilizator yawninghorseDragomir Alex yawninghorse Data 14 martie 2025 23:09:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax = 1e5 + 5;
const int Mmax = 2e5 + 5;
vector<int> lista[Mmax], lista_transp[Mmax], tc[Nmax];
int n, m;
int viz[Nmax], crt[Nmax];
int ord = 1, cont = 0;

void dfs1(int node)
{
    viz[node] = true;
    for(int i = 0; i < lista[node].size(); i++)
    {
        int v = lista[node][i];
        if(viz[v] == false)
            dfs1(v);
    }
    crt[ord++] = node;
}

void dfs2(int node)
{
    viz[node] = true;
    for(int i = 0; i < lista_transp[node].size(); i++)
    {
        int v = lista_transp[node][i];
        if(viz[v] == false)
            dfs2(v);
    }
    tc[cont].push_back(node);
}

void kosaraju()
{
    for(int i = 1; i <= n; i++)
    {
        if(viz[i] == false)
            dfs1(i);
    }
    for(int i = 1; i <= n; i++)
    {
        viz[i] = false;
    }
    for(int i = n; i >= 1; i--)
    {
        if(viz[crt[i]] == false)
        {
            dfs2(crt[i]);
            cont++;
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        lista[x].push_back(y);
        lista_transp[y].push_back(x);
    }
    kosaraju();
    cout << cont << '\n';
    for(int i = 0; i < cont; i++)
    {
        for(int j = 0; j < tc[i].size(); j++)
            cout << tc[i][j] << " ";
        cout << '\n'; 
    }
    return 0;
}