Cod sursa(job #2117626)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 29 ianuarie 2018 00:05:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
ofstream fout ("ctc.out");
ifstream fin ("ctc.in");
vector < int > G[100005],GT[100005],rsp[100005];
int n,m,i,x,y,k,used[100005],v[100005];
void DFS( int nod )
{
    used[ nod ] = 1;
    for( auto it : G[ nod ] )
        if( !used[ it ])
            DFS( it );
    v[ k-- ] = nod;
}
void DFS2( int nod )
{
    used[ nod ] = 1;
    rsp[ k ].push_back( nod );
    for( auto it : GT[ nod ] )
        if( !used[ it ])
            DFS2( it );
}
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        G[ x ].push_back( y );
        GT[ y ].push_back( x );
    }
    k = n;
    for( i = 1 ; i <= n ; i++ )
        if( !used[ i ] )
            DFS( i );
    memset( used , 0 , sizeof( used ) );
    for( i = 1 ; i <= n ; i++ )
    {
        if( !used[ v[ i ] ] )
        {
            k++;
            DFS2( v[ i ] );
        }
    }
    fout<<k<<'\n';
    for( i = 1 ; i <= k ; i++ )
    {
        for( auto it : rsp[ i ] )
            fout<<it<<" ";
        fout<<'\n';
    }
}