Pagini recente » Cod sursa (job #115274) | Cod sursa (job #718717) | Cod sursa (job #2569474) | Cod sursa (job #911612) | Cod sursa (job #392955)
Cod sursa(job #392955)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on February 8, 2010, 4:58 PM
*/
#include <stack>
#include <vector>
#include <utility>
#include <fstream>
#include <iterator>
/*
*
*/
using namespace std;
int nrscc=0;
stack< int > s;
vector< bool > uz;
vector< pair< int, int > > ss;
vector< vector< int > > v, scc;
inline int min( int x, int y )
{
return y^( (x^y) & -(x<y) );
}
inline void DFS( int x, int index )
{
vector<int>::const_iterator it=v[x].begin(), iend=v[x].end();
ss[x].first=index;
ss[x].second=index;
s.push(x);
uz[x]=true;
for( ; it < iend; ++it )
{
if( !ss[*it].first )
{
DFS( *it, index+1 );
ss[x].second=min( ss[x].second, ss[*it].second );
}
else if( uz[*it] )
ss[x].second=min( ss[x].second, ss[*it].second );
}
if( ss[x].second ==ss[x].first )
{
++nrscc;
scc.resize(nrscc);
do
{
scc[nrscc-1].push_back( s.top()+1 );
uz[s.top()]=false;
s.pop();
}while( scc[nrscc-1].back() != x+1 );
}
}
int main()
{
int n, m, x, y, i;
ifstream in("ctc.in");
in>>n>>m;
v.resize(n);
uz.resize(n);
ss.resize(n);
for( ; m; --m )
{
in>>x>>y;
v[x-1].push_back(y-1);
}
for( i=0; i < n; ++i )
if( !ss[i].first )
DFS( i, 1 );
ofstream out("ctc.out");
out<<nrscc<<'\n';
for( i=0; i < nrscc; ++i )
{
copy( scc[i].begin(), scc[i].end(), ostream_iterator<int>(out, " ") );
out<<'\n';
}
return 0;
}