Pagini recente » Cod sursa (job #2632368) | Cod sursa (job #2676540) | Cod sursa (job #407791) | Cod sursa (job #236844) | Cod sursa (job #376075)
Cod sursa(job #376075)
/*
* 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;
}