Pagini recente » Cod sursa (job #1603465) | Cod sursa (job #1084320) | Cod sursa (job #2982745) | Cod sursa (job #1687267) | Cod sursa (job #392934)
Cod sursa(job #392934)
/*
* 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;
}