Cod sursa(job #2859209)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 28 februarie 2022 23:44:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int nmax = 1e5;
vector < int > g[nmax + 1];
vector < int > gt[nmax + 1];
vector < int > ord;
vector < int > comp[nmax + 1]; int k;
bitset < nmax + 1 > vis;
void dfs ( int node ) {
    vis[node] = 1;
    for ( auto x: g[node] )
        if ( vis[x] == 0 )
            dfs ( x );
    ord.push_back ( node );
}
void dfs_t ( int node ) {
    vis[node] = 1;
    comp[k].push_back ( node );
    for ( auto x: gt[node] )
        if ( vis[x] == 0 )
            dfs_t ( x );
}
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
int main() {
    int n, m, a, b;
    fin >> n >> m;
    for ( int i = 1; i <= m; i++ ) {
        fin >> a >> b;
        g[a].push_back ( b );
        gt[b].push_back ( a );
    }

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

    vis.reset ();
    for ( int i = n - 1; i >= 0; i-- )
        if ( vis[ord[i]] == 0 )
            k++, dfs_t ( ord[i] );

    fout << k << '\n';
    for ( int i = 1; i <= k; i++, fout << '\n' ) {
        sort ( comp[i].begin (), comp[i].end () );
        for ( auto x: comp[i] )
            fout << x << ' ';
    }


    return 0;
}