Cod sursa(job #894463)

Utilizator lucian666Vasilut Lucian lucian666 Data 26 februarie 2013 21:28:11
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb


//plus-minus
#include<fstream>
#include<algorithm>
#include<vector>


#define NN 100001
#define pb push_back


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

int n , m , uz1[NN] , uz2[NN] , nrp ;

vector< int > G1[NN] , G2[NN];
typedef vector< int >:: iterator IT;

void read();

void dfs( vector< int > *g , int start , int cul , int * );
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;
        G1[x].pb(y);
        G2[y].pb(x);
    }
}

void dfs( vector< int > *g , int start , int cul , int *v )
{
    v[ start ] = cul;
        for( IT i = g[start].begin(); i!=g[start].end(); ++i )
            if ( !v[ *i ] )
                dfs( g , *i , cul , v );
}



void solve()
{
    for( int i=1 ; i<=n ; i++)
        if ( !uz1[i] && !uz2[i] )
        {
            ++nrp;
            dfs( G1 , i , nrp , uz1 );
            dfs( G2 , i , nrp , uz2 );

            for( int j = 1 ; j<=n ; j++)
                uz1[j] = uz2[j] = min( uz1[j] , uz2[j] );
        }

}



void wrs()
{
    out << nrp << '\n';

    for( int i=1 ; i<=nrp ; i++)
    {
        for( int j=1; j<=n;j++)
            if ( uz1[j] == i )
                out << j << " ";

        out << '\n';
    }
}