Pagini recente » Cod sursa (job #377295) | Cod sursa (job #2305616) | Cod sursa (job #2106685) | Cod sursa (job #2834961) | Cod sursa (job #375211)
Cod sursa(job #375211)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on December 19, 2009, 3:51 PM
*/
#include <stack>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pb push_back
/*
*
*/
using namespace std;
int counting;
vector<int> uz, uzt;
vector< vector<int> > v, vt, tc;
void DFS( int x )
{stack<int> s;
vector<int>::const_iterator it, iend;
s.push(x);
uz[x]=1;
while( !s.empty() )
{
x=s.top(); s.pop();
for( it=v[x].begin(), iend=v[x].end(); it < iend; ++it )
if( !uz[*it] )
{
uz[*it]=1;
s.push(*it);
}
}
}
void DFST( int x )
{stack<int> s;
vector<int>::const_iterator it, iend;
s.push(x);
uz[x]=2;
while( !s.empty() )
{
x=s.top(); s.pop();
tc[counting-1].pb(x+1);
for( it=vt[x].begin(), iend=vt[x].end(); it < iend; ++it )
if( 1 == uz[*it] )
{
uz[*it]=2;
s.push(*it);
}
}
}
inline bool check( int x )
{
return 1 == x;
}
int main()
{int n, m, x, y, i;
ifstream in("ctc.in");
in>>n>>m;
v.resize(n);
vt.resize(n);
uz.resize(n);
uzt.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] )
{++counting;
tc.resize(counting);
DFS(i);
DFST(i);
replace_if( uz.begin(), uz.end(), check, 0 );
}
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';
}
}