Pagini recente » Cod sursa (job #670792) | Cod sursa (job #1414339) | Cod sursa (job #93893) | Cod sursa (job #1259293) | Cod sursa (job #376094)
Cod sursa(job #376094)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on December 20, 2009, 2:02 PM
*/
#include <map>
#include <vector>
#include <fstream>
#include <iterator>
#define pb push_back
/*
* Algoritm Plus-Minus imbunatatit
*/
using namespace std;
int counting, timing;
vector<int> order, uz;
map< int, int > final;
vector< vector<int> > v, vt, tc;
void DFS( int x )
{vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
++timing;
uz[x]=1;
for( ; it < iend; ++it )
if( !uz[*it] )
DFS(*it);
++timing;
final[timing]=x;
}
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 )
{map< int, int >::const_iterator it=final.begin(), iend=final.end();
for( int i=n-1; it != iend; ++it, --i )
order[i]=it->second;
}
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);
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 );
for( i=0; i < n; ++i )
if( uz[order[i]] )
{++counting;
tc.resize(counting);
DFST(order[i]);
}
//copy( order.begin(), order.end(), ostream_iterator<int>(out, " ") );
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';
}
}