Cod sursa(job #3271791)

Utilizator yawninghorseDragomir Alex yawninghorse Data 27 ianuarie 2025 12:50:56
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>

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

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

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

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

void kosaraju()
{
    dfs(1);
    for(int i = 1; i <= n; i++)
        viz[i] =false;
    for(int i = n; i >= 1; i--)
    {
        if(viz[ord[i]] == false)
        {
            dfs2(ord[i]);
            ans++;
        }
    }
}

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