Cod sursa(job #392959)

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

/*
 *
 */
using namespace std;
int nrscc=0, idx=1;
stack< int > s;
vector< bool > uz;
vector< pair< int, int > > ss;
vector< vector< int > > v, scc;
inline int min( int x, int y )
{
    return y^( (x^y) & -(x<y) );
}
inline void DFS( int x )
{
    vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
    ss[x].first=idx;
    ss[x].second=idx;
    ++idx;
    s.push(x);
    uz[x]=true;
    for( ; it < iend; ++it )
    {
        if( !ss[*it].first )
        {
            DFS( *it );
            ss[x].second=min( ss[x].second, ss[*it].second );
        }
        else if( uz[*it] )
                ss[x].second=min( ss[x].second, ss[*it].second );
    }
    if( ss[x].second ==ss[x].first )
    {
        ++nrscc;
        scc.resize(nrscc);
        do
        {
            scc[nrscc-1].push_back( s.top()+1 );
            uz[s.top()]=false;
            s.pop();
        }while( scc[nrscc-1].back() != x+1 );
    }
}
int main()
{
    int n, m, x, y, i;
    ifstream in("ctc.in");
    in>>n>>m;
    v.resize(n);
    uz.resize(n);
    ss.resize(n);
    for( ; m; --m )
    {
        in>>x>>y;
        v[x-1].push_back(y-1);
    }
    for( i=0; i < n; ++i )
        if( !ss[i].first )
           DFS( i );
    ofstream out("ctc.out");
    out<<nrscc<<'\n';
    for( i=0; i < nrscc; ++i )
    {
        copy( scc[i].begin(), scc[i].end(), ostream_iterator<int>(out, " ") );
        out<<'\n';
    }
    return 0;
}