Cod sursa(job #3287022)

Utilizator yawninghorseDragomir Alex yawninghorse Data 14 martie 2025 22:48:42
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>

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];
int n, m;
int viz[Nmax], crt[Nmax];
int ord = 1, cont = 0;
stack <int> s;

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

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);
    }
    s.push(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 = 1; i <= ord; i++)
    {
        if(viz[crt[i]] == false)
        {
            cont++;
            dfs2(crt[i]);
            s.push(-1);
        }
    }
}

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';
    s.pop();
    while(!s.empty())
    {
        if(s.top() == -1)
            cout << '\n';
        else
            cout << s.top() << " ";
        s.pop(); 
    }
    return 0;
}