Cod sursa(job #376075)

Utilizator alexandru92alexandru alexandru92 Data 20 decembrie 2009 16:22:42
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 20, 2009, 2:02 PM
 */
#include <queue>
#include <vector>
#include <fstream>
#include <iterator>
#define pb push_back

/*
 * Algoritm Plus-Minus imbunatatit
 */
using namespace std;
int counting, timing=0;
vector<int> order, final, uz, c;
vector< vector<int> > v, vt, tc;
void DFS( int x )
{vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
    uz[x]=1;
    for( ; it < iend; ++it )
        if( !uz[*it] )
        {
            DFS(*it);
            ++timing;
        }
    final[x]=timing;
}
inline void DFST( int x )
{vector<int>::const_iterator it=vt[x].begin(), iend=vt[x].end();
    uz[x]=0;
    tc[counting-1].pb(x+1);
    for( ; it < iend; ++it )
        if( uz[*it] )
           DFST(*it);
}
void Order( int n )
{int i;
    for( i=0; i < n; ++i )
        order[n-final[i]]=i;
}
int main()
{int n, m, x, y, i;
    ifstream in("ctc.in");
    in>>n>>m;
    v.resize(n);
    vt.resize(n);
    uz.resize(n);
    order.resize(n);
    final.resize(n);
    while( m-- )
    {
        in>>x>>y;
        v[x-1].pb(y-1);
        vt[y-1].pb(x-1);
    }
    for( i=0; i < n; ++i )
        if( !uz[i] )
           DFS(i);
       
    Order(n);
    //ofstream out("ctc.out");
    //copy( final.begin(), final.end(), ostream_iterator<int>(out," "));
    for( i=0; i < n; ++i )
        if( uz[order[i]] )
        {
            ++counting;
            tc.resize(counting);
            DFST(order[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;
}