Pagini recente » Cod sursa (job #2246684) | Cod sursa (job #3271464) | Cod sursa (job #1253219) | Cod sursa (job #370910) | Cod sursa (job #263058)
Cod sursa(job #263058)
#include<stdio.h>
#define max 100010
long s[max], x[max], n, m, nr;
int vza[max], vzt[max];
struct elem
{ long vf;
elem *urm;
} *ga[max], *gt[max], *q;
FILE *f, *g;
void read()
{ long i, x, y;
f=fopen("ctc.in", "r");
fscanf(f, "%ld%ld", &n, &m);
for(i=1; i<=m; i++)
{ fscanf(f, "%ld%ld", &x, &y);
q=new elem;
q->vf=y;
q->urm=ga[x];
ga[x]=q;
q=new elem;
q->vf=x;
q->urm=gt[y];
gt[y]=q;
}
}
void empty()
{ long i;
for(i=1; i<=n; i++)
{ vza[i]=0; vzt[i]=0;
if(x[i]==2)
x[i]=nr;
if(x[i]<0)
{ vza[i]=1; vzt[i]=1;
}
if(x[i]>0)
x[i]=0;
}
}
void dfa(int z,int k)
{ elem *q;
s[k]=z;
vza[z]=1;
x[z]++;
q=ga[z];
while(q)
{ if(vza[q->vf]==0)
{ dfa(q->vf, k+1);
}
q=q->urm;
}
}
void dft(int z,int k)
{ elem *q;
s[k]=z;
vzt[z]=1;
x[z]++;
q=gt[z];
while(q)
{ if(vzt[q->vf]==0)
{ dft(q->vf, k+1);
}
q=q->urm;
}
}
int main()
{ long i, j;
read();
for(i=1; i<=n; i++)
{ if(vza[i]==0)
{ dfa(i, 1);
dft(i, 1);
nr--;
empty();
}
}
g=fopen("ctc.out", "w");
fprintf(g, "%ld\n", nr*(-1));
for(i=-1; i>=nr; i--)
{ for(j=1; j<=n; j++)
if(x[j]==i)
fprintf(g, "%ld ", j);
fprintf(g, "\n");
}
fclose(g);
return 0;
}