Cod sursa(job #376128)

Utilizator alexandru92alexandru alexandru92 Data 20 decembrie 2009 19:38:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 20, 2009, 6:22 PM
 */
#include <stack>
#include <vector>
#include <utility>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pb push_back

/*
 * 
 */
using namespace std;
int counting, indecs=1;
vector<int> uz;
vector< pair< int, int > > vertex;
vector< vector<int> > v, tc;
stack<int> s;
void DFS( int x )
{vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
    vertex[x].first=vertex[x].second=indecs;
    ++indecs;
    s.push(x);
    uz[x]=1;
    for( ; it < iend; ++it )
        if( !vertex[*it].first )
        {
            DFS(*it);
            vertex[x].second=min( vertex[x].second, vertex[*it].second );
        }
        else if( uz[*it] ) //if it's on stack
               vertex[x].second=min( vertex[x].second, vertex[*it].second );
    if( vertex[x].first == vertex[x].second )
    {int nod;
        ++counting;
        tc.resize(counting);
        do
        {nod=s.top();
            uz[nod]=0;
            tc[counting-1].pb(nod+1);
            s.pop();
        }while( nod != x );
    }
}
int main()
{int n, m, x, y, i;
    ifstream in("ctc.in");
    in>>n>>m;
    v.resize(n);
    vertex.resize(n);
    uz.resize(n);
    while( m-- )
    {
        in>>x>>y;
        v[x-1].pb(y-1);
    }
    for( i=0; i < n; ++i )
        if( !vertex[i].first )
            DFS(i);
    ofstream out("ctc.out");
    out<<counting<<'\n';
    for( i=0; i < counting; ++i )
    {
        copy( tc[i].begin(), tc[i].end(), ostream_iterator<int>(out, " ") );
        out<<'\n';
    }
    return 0;
}