Pagini recente » Cod sursa (job #2878501) | Cod sursa (job #387413) | Cod sursa (job #693052) | Cod sursa (job #2589566) | Cod sursa (job #2217810)
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N;
int M;
int nr_noduri;
vector <vector <int> > Ad(100002);
int disc[100002];
int low[100002];
deque <int> Stack;
bool in_stack[100002];
vector <vector <int> > SCC(100002);
int nr_scc;
void Read()
{
fin >> N >> M;
int x,y;
for( int i = 1; i <= M; ++i )
{
fin >> x >> y;
Ad[x].push_back(y);
}
fin.close();
}
void Discover( int nod )
{
disc[nod] = low[nod] = ++nr_noduri;
Stack.push_back( nod );
in_stack[nod] = 1;
int w;
for( int i = 0; i < Ad[nod].size(); ++i )
{
w = Ad[nod][i];
if( disc[w] == 0 )
{
Discover( w );
low[nod] = min( low[nod], low[w] );
}
else
if( in_stack[w] )
low[nod] = min( low[nod], disc[w] );
}
if( disc[nod] == low[nod] )
{
++nr_scc;
while( Stack.back() != nod )
{
SCC[nr_scc - 1].push_back( Stack.back() );
in_stack[Stack.back()] = 0;
Stack.pop_back();
}
SCC[nr_scc - 1].push_back( Stack.back() );
Stack.pop_back();
}
}
void Test()
{
for( int i = 1; i <= N; ++i )
fout << "NODUL : " << i << ' ' << disc[i] << ' ' << low[i] << '\n';
}
void Do()
{
for( int i = 1; i <= N; ++i )
if( disc[i] == 0 )
Discover( i );
}
void Print()
{
fout << nr_scc << '\n';
for( int i = 0; i < nr_scc; ++i )
{
for( int j = 0; j < SCC[i].size(); ++j )
fout << SCC[i][j] << ' ';
fout << '\n';
}
fout.close();
}
int main()
{
Read();
Do();
Print();
return 0;
}