Cod sursa(job #981499)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 7 august 2013 12:55:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define Nmax 100002

vector<int> S[Nmax];
vector<int> G[Nmax];
vector<int> GT[Nmax];

vector<int> postordine(Nmax);
vector<bool> viz(Nmax);

int N, M, P, nr;

void read()
{
    ifstream f("ctc.in");

    f >> N >> M;

    for ( int i = 1, a, b; i <= M; ++i )
    {
        f >> a >> b;

        G[a].push_back( b );
        GT[b].push_back( a );
    }

    f.close();
}

void DFS( int node )
{
    viz[node] = 1;

    for ( unsigned i = 0; i < G[node].size(); ++i )
    {
        if ( !viz[ G[node][i] ] )
        {
            DFS( G[node][i] );
        }
    }

    postordine[ ++P ] = node;
}

void DFST( int node )
{
    viz[node] = 0;

    S[nr].push_back( node );

    for ( unsigned i = 0; i < GT[node].size(); ++i )
    {
        if ( viz[ GT[node][i] ] )
        {
            DFST( GT[node][i] );
        }
    }
}

void solve()
{
    for ( int i = 1; i <= N; ++i )
            if ( !viz[i] )
                    DFS( i );

    for ( int i = N; i >= 1; i-- )
    {
        if ( viz[ postordine[i] ] )
        {
            nr++;
            DFST( postordine[i] );
        }
    }
}

void print()
{
    ofstream g("ctc.out");

    g << nr << "\n";

    for ( int i = 1; i <= nr; ++i )
    {
        for ( unsigned j = 0; j < S[i].size(); ++j )
                g << S[i][j] << " ";

        g << "\n";
    }

    g.close();
}

int main()
{
    read();
    solve();
    print();

    return 0;
}