Cod sursa(job #1609067)

Utilizator Bot32King Max Bot32 Data 22 februarie 2016 16:31:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

#define nrmax 100001
#define pb push_back

ifstream f("ctc.in");
ofstream g("ctc.out");

int n , m , x, y , k , np;
vector < int > G[nrmax];
vector < int > T[nrmax];
vector < int > sol[nrmax];
bool used[nrmax];
int p[nrmax];

void citire_date()
{
    f >> n >> m;
    for ( ; m-- ; )
    {
        f >> x >> y;
        G[x].pb(y);
        T[y].pb(x);
    }
}

void dfs( int i )
{
    used[i] = true;
    for ( vector < int > ::iterator j = G[i].begin(); j != G[i].end() ; j++ )
    {
        if( !used[(*j)] )
            dfs((*j));
    }
    p[++np] = i;
}

void dfs_T ( int i )
{
    used[i] = false;
    sol[k].pb(i);
    for ( vector < int > ::iterator j = T[i].begin(); j != T[i].end() ; j++ )
    {
        if( used[(*j)] )
            dfs_T((*j));
    }
}


int main()
{
    citire_date();
    for ( int i = 1; i <= n ; i++ )
        if ( !used[i] )
            dfs(i);
    for ( int i = n ; i >=  1  ; i-- )
        if ( used[p[i]] )
        {
            k++;
            dfs_T(p[i]);
        }

    g << k << "\n" ;
    for ( int i = 1; i <= k ; i++ )
    {
        for ( vector < int > ::iterator j = sol[i].begin() ; j != sol[i].end() ; j++ )
        {
            g << (*j) << " " ;
        }
        g << "\n";
    }
    return 0;
}