Pagini recente » Cod sursa (job #607026) | Cod sursa (job #2500401) | Cod sursa (job #2891568) | Cod sursa (job #2284363) | Cod sursa (job #376007)
Cod sursa(job #376007)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on December 20, 2009, 2:02 PM
*/
#include <vector>
#include <fstream>
#include <iterator>
#define pb push_back
/*
* Algoritm Plus-Minus imbunatatit
*/
using namespace std;
int counting;
vector<int> order, final, uz, c;
vector< vector<int> > v, vt, tc;
inline void DFS_final( int x, int& time )
{vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
uz[x]=1;
for( ; it < iend; ++it )
if( !uz[*it] )
{
DFS_final(*it, time);
++time;
}
final[x]=time;
}
inline void DFS( 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] )
DFS(*it);
}
void Order( int n )
{int i;
for( i=0; i < n; ++i )
order[n-final[i]-1]=i;
}
int main()
{int n, m, x, y, i, time=0;
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_final(i, time);
Order(n);
for( i=0; i < n; ++i )
if( uz[order[i]] )
{
++counting;
tc.resize(counting);
DFS(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;
}