Pagini recente » Cod sursa (job #2888578) | Cod sursa (job #641493) | Cod sursa (job #2617722) | Cod sursa (job #2311143) | Cod sursa (job #1088777)
/*
~Keep It Simple!~
*/
#include<stdio.h>
#include<list>
#define NMax 100005
using namespace std;
int N,M,idx[NMax],Lowlink[NMax],In_Stack[NMax],indeces;
list<int> G[NMax],S,A;
list< list<int> > Lists;
void StronglyConnectedComponentsInit(int node)
{
idx[node] = Lowlink[node] = ++indeces;
In_Stack[node] = 1;
S.push_back(node);
for(list<int>::iterator it = G[node].begin(); it!=G[node].end(); it++)
{
if(!idx[*it])
{
StronglyConnectedComponentsInit(*it);
Lowlink[node] = min(Lowlink[node],Lowlink[*it]);
}
else if(In_Stack[*it])
{
Lowlink[node] = min(Lowlink[node],Lowlink[*it]);
}
}
if( idx[node] == Lowlink[node])
{
int aux;
A.clear();
do
{
A.push_back(aux = S.back());
S.pop_back(); In_Stack[aux] = 0;
}while(aux != node);
Lists.push_back(A);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&N,&M);
int x,y;
for(int i=1; i<=M; i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
indeces++;
for(int i=1; i<=N; i++)
if(!idx[i])
StronglyConnectedComponentsInit(i);
printf("%d\n",Lists.size());
for(list<list<int>>::iterator it=Lists.begin(); it!=Lists.end(); it++)
{
for(list<int>::iterator j = it->begin(); j!=it->end(); j++)
printf("%d ", *j);
printf("\n");
}
}