Cod sursa(job #3041965)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 3 aprilie 2023 11:14:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>

using namespace std;
const int nmax = 1e5;

int vis[nmax];
vector < int > g[nmax];
vector < int > gt[nmax];
vector < int > c[nmax];
int ord[nmax];
int k;

void dfs ( int node ) {
    vis[node] = 1;
    for ( int &x: g[node] )
        if ( !vis[x] )
            dfs ( x );
    ord[--k] = node;
}

int cul;

void dfsT ( int node ) {
    c[cul].push_back ( node );
    vis[node] = 1;
    for ( int &x: gt[node] )
        if ( !vis[x])
            dfsT ( x );
}

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

int main() {
    int n, m, x, y;
    fin >> n >> m;
    for ( int i = 0; i < m; i++ ) {
        fin >> x >> y;
        x--, y--;
        g[x].push_back ( y );
        gt[y].push_back ( x );
    }

    k = n;
    for ( int i = 0; i < n; i++ )
        if ( !vis[i] )
            dfs ( i );

    for ( int i = 0; i < n; i++ )
        vis[i] = 0;

    cul = 0;
    for ( int i = 0; i < n; i++ )
        if ( !vis[ord[i]] )
            dfsT ( ord[i] ), cul++;

    fout << cul << '\n';
    for ( int i = 0; i < cul; i++, fout << '\n' )
        for ( int &x: c[i] )
            fout << 1 + x << ' ';


    return 0;
}