Pagini recente » Cod sursa (job #1157843) | Cod sursa (job #2059261) | Cod sursa (job #2921943) | Cod sursa (job #2631948) | Cod sursa (job #1772517)
#include <stdio.h>
#include <stdlib.h>
#define min(a,b) ((a)<(b) ? (a) : (b))
struct list
{
int x;
list * next;
};
int n,m,i,__i,j,k=-1,lowlink[100009],index[100009],st[100009],in[100009];
list * g[100009],*p,*cmp[100009];
void add(list **l,int x)
{
p=(list *) malloc(sizeof(list));
p->next=*l;
p->x=x;
*l=p;
}
const int buff_size=4096;
char buff[buff_size];
int _i=buff_size;
int next_int(FILE * in)
{
char x,y,k=1;
int z=0;
if (_i==buff_size)
y=fread(buff,buff_size,1,in),_i=0;
x=1;
while ((x<48 || x> 57) && x!='-')
{
x=buff[_i];
_i++;
if (_i==buff_size)
{
y=fread(buff,buff_size,1,in);
_i=0;
}
}
while (x>=48 && x<=57 || x=='-')
{
if (x=='-')
k=-1; else
z=(z<<1)+(z<<3)+x-48;
x=buff[_i];
_i++;
if (_i==buff_size)
{
y=fread(buff,buff_size,1,in);
_i=0;
}
}
return z*k;
}
void dfs(int x)
{
index[x]=i;
lowlink[x]=i;
i++;
st[++k]=x;
in[x]=1;
for (list * p = g[x]; p ;p=p->next)
if (index[p->x]==0)
{
dfs(p->x);
lowlink[x]=min(lowlink[x],lowlink[p->x]);
} else
if (in[p->x]==1)
lowlink[x]=min(lowlink[x],lowlink[p->x]);
if (index[x]==lowlink[x])
{
while (st[k]!=x)
add(&cmp[j],st[k]),in[st[k]]=0,k--;
in[x]=0; k--;
add(&cmp[j],x);
j++;
}
}
int main(int argc, char const *argv[])
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
n=next_int(stdin);
m=next_int(stdin);
while (m--)
{
i=next_int(stdin);
j=next_int(stdin);
add(&g[i],j);
}
j=0;
i=1;
for (__i=1;__i<=n;++__i)
if (index[__i]==0)
dfs(__i);
printf("%d\n",j);
for (i=0;i<j;++i)
{
for (p=cmp[i]; p ; p=p->next)
printf("%d ",p->x);
puts("");
}
fclose(stdin);
fclose(stdout);
return 0;
}