Cod sursa(job #3353863)

Utilizator andreidumitrache1709andreidumitrache andreidumitrache1709 Data 12 mai 2026 11:05:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;

int roots[MAXN + 1] , sz[MAXN + 1] , cnt;
bool viz[MAXN + 1];
stack< int >s;
vector< int >edges[MAXN + 1] , redges[MAXN + 1];
vector< int >v[MAXN + 1];
void dfs( int nod ) {
    viz[nod] = 1;
    for( auto x : edges[nod] )
        if( !viz[x] )
            dfs( x );
    s.push( nod );
}
void dfs2( int nod ) {
    if( !roots[nod] )
        v[cnt].push_back( nod );
    roots[nod] = cnt;
    sz[cnt]++;
    for( auto x : redges[nod] )
        if( !roots[x] )
            dfs2( x );
}
int main() {
    ifstream cin( "ctc.in" );
    ofstream cout( "ctc.out" );
    int n , m , k , i , a , b;
    cin >> n >> m;
    for( i = 1 ; i <= m ; i++ ) {
        cin >> a >> b;
        edges[a].push_back( b );
        redges[b].push_back( a );
    }
    for( i = 1 ; i <= n ; i++ )
        if( !viz[i] )
            dfs( i );
    cnt = 0;
    while( !s.empty() ) {
        a = s.top();
        s.pop();
        if( !roots[a] )
            cnt++;
        dfs2( a );
    }
    cout << cnt << '\n';
    for( i = 1 ; i <= cnt ; i++ ) {
        sort( v[i].begin() , v[i].end() );
        for( auto x : v[i] )
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}