Pagini recente » Cod sursa (job #483214) | Cod sursa (job #2103841) | Cod sursa (job #1711779) | Cod sursa (job #3178021) | Cod sursa (job #376128)
Cod sursa(job #376128)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on December 20, 2009, 6:22 PM
*/
#include <stack>
#include <vector>
#include <utility>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pb push_back
/*
*
*/
using namespace std;
int counting, indecs=1;
vector<int> uz;
vector< pair< int, int > > vertex;
vector< vector<int> > v, tc;
stack<int> s;
void DFS( int x )
{vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
vertex[x].first=vertex[x].second=indecs;
++indecs;
s.push(x);
uz[x]=1;
for( ; it < iend; ++it )
if( !vertex[*it].first )
{
DFS(*it);
vertex[x].second=min( vertex[x].second, vertex[*it].second );
}
else if( uz[*it] ) //if it's on stack
vertex[x].second=min( vertex[x].second, vertex[*it].second );
if( vertex[x].first == vertex[x].second )
{int nod;
++counting;
tc.resize(counting);
do
{nod=s.top();
uz[nod]=0;
tc[counting-1].pb(nod+1);
s.pop();
}while( nod != x );
}
}
int main()
{int n, m, x, y, i;
ifstream in("ctc.in");
in>>n>>m;
v.resize(n);
vertex.resize(n);
uz.resize(n);
while( m-- )
{
in>>x>>y;
v[x-1].pb(y-1);
}
for( i=0; i < n; ++i )
if( !vertex[i].first )
DFS(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;
}