Cod sursa(job #1227157)

Utilizator lucian666Vasilut Lucian lucian666 Data 9 septembrie 2014 15:55:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb


#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <bitset>
#include <set>


#define DIM 100009
#define pb push_back

using namespace std;
ofstream out("ctc.out");

int n , m , nrc , nr;
int postord[DIM] ;

bitset < DIM > uz;

vector < int > G[DIM] , GT[DIM] ;
typedef vector < int >:: iterator IT;

set < int > sol[DIM];
typedef set < int >:: iterator JT;

void read();
void dfs( int root  );
void dft( int root , int nrc , set < int >* sol );
void solve();
void wrs();


int main()
{

    read();
    solve();
    wrs();


    return 0;

}

void read()
{

    ifstream in("ctc.in");
    in >> n >> m ;

    for( int x , y ; m ; --m )
    {

        in >> x >> y;

        G[x].pb(y);
        GT[y].pb(x);

    }

}


void dfs( int root )
{

    uz[ root ] = 1;

    for ( IT i = G[root].begin() ; i!= G[root].end(); ++i )
        if( !uz[*i] )
            dfs(*i);

    postord[ ++nr ] = root;

}

void dft( int root , int nrc , set < int >* sol )
{

    uz[root] = 0;
    sol[nrc].insert(root);

    for( IT i = GT[root].begin() ; i!=GT[root].end(); ++i )
        if( uz[*i] )
        dft(*i,nrc,sol);

}


void solve()
{

    for( int i=1 ; i<=n ; i++)
        if( !uz[i] )
            dfs(i);

    for( int i = n ; i >=1 ; i-- )
        if( uz[ postord[i] ] )
        {
            ++nrc;
            dft(postord[i],nrc,sol);
        }

}

void wrs()
{

    out << nrc << '\n';

    for( int i=1 ; i<=nrc ; i++)
    {

        for( JT j = sol[i].begin() ; j!=sol[i].end() ; ++j )
                out << *j << " ";

        out << '\n';

    }

}