Pagini recente » Cod sursa (job #49192) | Cod sursa (job #1402628) | Cod sursa (job #427630) | Cod sursa (job #2124697) | Cod sursa (job #374673)
Cod sursa(job #374673)
#include <stdio.h>
#define max 100010
int stack[max],ind[max],low[max],i,j,n,m,k,index,top,comp;
char s[max];
struct lista
{
int nod;
lista *next;
};
lista *g[max],*q[max],*p;
void push(lista *&g,int j)
{
lista *p=new lista;
p->nod=j;
p->next=g;
g=p;
}
void dfs(int v)//tarjan
{
int w; lista *p;
ind[v]=low[v]=++index;
stack[++top]=v;
for(p=g[v]; p!=NULL; p=p->next)
if(!s[p->nod])
{
if(!ind[p->nod]) dfs(p->nod);
if(low[p->nod]<low[v]) low[v]=low[p->nod];
}
if(low[v]==ind[v])
{
comp++;
while(stack[top]!=v)
{
s[stack[top]]=1;
push(q[comp],stack[top]);
top--;
}
push(q[comp],v);
s[v]=1;
top--;
}
}
int main()
{
freopen("ctc.in","r",stdin);
//freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(k=1; k<=m; k++)
{
scanf("%d%d",&i,&j);
push(g[i],j);
}
for(i=1; i<=n; i++)
if(!ind[i]) dfs(i);
printf("%d\n",comp);
for(i=1; i<=comp; i++)
{
for(p=q[i]; p!=NULL; p=p->next)
printf("%d ",p->nod);
printf("\n");
}
return 0;
}