Cod sursa(job #1441144)

Utilizator supremusChihalau Andrei supremus Data 23 mai 2015 19:43:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector<int> G[100001], H[100001];
int viz[100001];

int n, m, po[100001], nr;
int comp;
vector <int> v[100001];

void dfs ( int x )
{
    viz[x] = 1;
    for ( int i = 0; i < G[x].size(); i++ )
        if ( !viz[G[x][i]] )
            dfs ( G[x][i] );
    nr++;
    po[nr] = x;
}

void dfst ( int x )
{
    viz[x] = 0;
    for ( int i = 0; i < H[x].size(); i++ )
        if ( viz[H[x][i]] )
            dfst ( H[x][i] );
    v[comp].push_back ( x );
}

int main()
{
    int i, a, b;

    f >> n >> m;
    for ( i = 1; i <= m; i++ )
    {
        f >> a >> b;
        G[a].push_back ( b );
        H[b].push_back ( a );
    }
    for ( i = 1; i <= n; i++ )
        if ( !viz[i] )
            dfs ( i );
    for ( i = n; i >= 1; i-- )
        if ( viz[po[i]] )
        {
            comp++;
            dfst ( po[i] );
        }
    g << comp << "\n";
    for ( i = 1; i <= comp; i++ )
    {
        for ( int j = v[i].size() - 1; j >= 0; j-- )
            g << v[i][j] << " ";
        g << "\n";
    }

    f.close();
    g.close();
    return 0;
}