Pagini recente » Cod sursa (job #2967463) | Cod sursa (job #397664) | Cod sursa (job #950475) | Cod sursa (job #2708302) | Cod sursa (job #256737)
Cod sursa(job #256737)
#include <stdio.h>
#define MAX 100002
#define IN "ctc.in"
#define OUT "ctc.out"
FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");
struct nod
{
int a;
nod *x;
}*l1[MAX],*l2[MAX],*comp[MAX];
int post[MAX],n,m,cnt;
char v[MAX];
void df1(int);
void df2(int);
int main()
{
fscanf(fin,"%d%d",&n,&m);
nod *q;
int A,B,i;
for(i=1;i<=m;++i)
{
fscanf(fin,"%d%d",&A,&B);
q=new nod;
q->a=B;
q->x=l1[A];
l1[A]=q;
q=new nod;
q->a=A;
q->x=l2[B];
l2[B]=q;
}
fclose(fin);
for(i=1;i<=n;++i)
if(v[i]==0)
df1(i);
for(i=n;i>0;--i)
if(v[post[i]]==1)
{
++cnt;
df2(post[i]);
}
fprintf(fout,"%d\n",cnt);
for(i=1;i<=cnt;++i,fprintf(fout,"\n"))
for (q=comp[i];q;q=q->x)
fprintf(fout,"%d ",q->a);
fclose(fout);
return 0;
}
void df1(int nodd)
{
nod *q;
v[nodd]=1;
for(q=l1[nodd];q;q=q->x)
if(v[q->a]==0)
df1(q->a);
post[++post[0]]=nodd;
}
void df2(int nodd)
{
nod *q;
v[nodd]=0;
q=new nod;
q->a=nodd;
q->x=comp[cnt];
comp[cnt]=q;
for(q=l2[nodd];q;q=q->x)
if(v[q->a]==1)
df2(q->a);
}