Cod sursa(job #981727)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 7 august 2013 19:34:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

#define Nmax 100002

vector<bool> visit(Nmax);
vector<bool> in_stack(Nmax);

vector<int> low(Nmax);
vector<int> ind(Nmax);

stack<int> ST;

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

int N, M, NR, indecs;

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 );
    }

    f.close();
}

void Tarjan( int node )
{
    visit[node] = 1;
    in_stack[node] = 1;
    indecs++;
    ind[node] = low[node] = indecs;

    ST.push( node );

    for ( unsigned i = 0; i < G[node].size(); ++i )
    {
        if ( !visit[ G[node][i] ] )
        {
            Tarjan( G[node][i] );
            low[node] = min( low[node], low[ G[node][i] ] );
        }
        else
            if ( in_stack[ G[node][i] ] )
            {
                low[node] = min( low[node], low[ G[node][i] ] );
            }
    }

    if ( low[node] == ind[node] )
    {
        NR++;

        while( ST.top() != node )
        {
            in_stack[ ST.top() ] = 0;
            S[NR].push_back( ST.top() );
            ST.pop();
        }

        ST.pop();
        in_stack[node] = 0;
        S[NR].push_back( node );
    }
}

void solve()
{
    for ( int i = 1; i <= N; ++i )
            if ( !visit[i] )
                    Tarjan( 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;
}