Pagini recente » Cod sursa (job #980630) | Cod sursa (job #276363) | Cod sursa (job #635470) | Cod sursa (job #1304338) | Cod sursa (job #241099)
Cod sursa(job #241099)
#include <stdio.h>
#include <vector>
#include <stack>
#define minim(a,b) ((a<b)?a:b)
#define pb(a) push_back(a)
using namespace std;
long n,m,i,j,nod,scc,index=1;
long x[200002],y[200002],g[100002],ind[100002],low[100002],inq[100002];
int * v[100002];
vector <int>sol[100002];
stack <int> Q;
void tarjan(long x){
ind[x]=low[x]=index;
inq[x]=1;
index++;
Q.push(x);
for (int i=0;i<g[x];++i){
nod=v[x][i];
if (!ind[nod]){
tarjan(nod);
low[x]=minim(low[x],low[nod]);
}
else if (inq[nod])low[x]=minim(low[x],low[nod]);
}
if (ind[x]==low[x]){
scc++;
do{
nod=Q.top();Q.pop();
sol[scc].pb(nod);
inq[nod]=0;
}while (nod!=x);
}
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%ld %ld",&n,&m);
for (i=1;i<=mi;++i){scanf("%ld %ld",&x[i],&y[i]);g[x[i]]++;}
for (i=1;i<=n;i++)v[i]=(int*)malloc(g[i]*sizeof(int)),g[i]=0;
for (i=1;i<=m;++i)v[x[i]][g[x[i]]++]=y[i];
//////////
for (i=1;i<=n;++i)if (!ind[i])tarjan(i);
//////////
printf("%ld\n",scc);
for (i=1;i<=scc;++i){
for (j=0;j<sol[i].size();++j)
printf("%ld ",sol[i][j]);
printf("\n");
}
return 0;
}