Cod sursa(job #392934)

Utilizator alexandru92alexandru alexandru92 Data 8 februarie 2010 16:52:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 8, 2010, 4:35 PM
 */
#include <vector>
#include <fstream>
#include <iterator>

/*
 *
 */
using namespace std;
int j;
vector< int > df;
vector< bool > uz;
vector< vector< int > > v, vt, scc;
void DFS( int x )
{
    vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
    uz[x]=true;
    ++j;
    for( ; it < iend; ++it )
        if( !uz[*it] )
            DFS(*it);
    df.push_back(x);
}
void DFS2( int x, int i )
{
    vector<int>::const_iterator it=vt[x].begin(), iend=vt[x].end();
    uz[x]=false;
    ++j;
    for( ; it < iend; ++it )
        if( uz[*it] )
            DFS2(*it, i );
    scc[i].push_back(x+1);
}
int main( void )
{
    int n, m, x, y, i;
    ifstream in("ctc.in");
    in>>n>>m;
    v.resize(n);
    vt.resize(n);
    for( ; m; --m )
    {
        in>>x>>y;
        x-=1; y-=1;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    uz.resize(n);
    for( i=0; i < n; ++i )
        if( !uz[i] )
        {
            DFS(i);
            if( n == j )
                break;
        }
    for( j=0, i=n-1; i >= 0; --i )
        if( uz[df[i]] )
        {
            ++m;
            scc.resize(m);
            DFS2( df[i], m-1  );
            if( n == j )
                break;
        }
    ofstream out("ctc.out");
    out<<m<<'\n';
    for( i=0; i < m; ++i )
    {
        copy( scc[i].begin(), scc[i].end(), ostream_iterator<int>(out, " ") );
        out<<'\n';
    }
    return 0;
}