Pagini recente » Cod sursa (job #3234554) | Cod sursa (job #696088) | Cod sursa (job #929259) | Cod sursa (job #386581) | Cod sursa (job #1605136)
#include<stdio.h>
using namespace std;
FILE *f1=fopen("ctc.in","r");
FILE *f2=fopen("ctc.out","w");
int n,m,nr,coada[100001],v[100001],nrc,i,j;
struct nod{
int inf2;
nod *urm2;
}*L1[100001],*L2[100001];
struct cod{
int inf;
cod *urm;
}*sol[100001];
void adaugaresf(int val,nod *&vf){
nod *q;
q=new nod;
q->inf2=val;
q->urm2=vf;
vf=q;
}
void citire(){
int i,a,b;
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=n;i++){
L1[i]=0;L2[i]=0;
}
for (i=1;i<=m;i++){
fscanf(f1,"%d%d",&a,&b);
adaugaresf(b,L1[a]);
adaugaresf(a,L2[b]);
}
fclose(f1);
}
void dfs(int k){
nod *q;
v[k]=1;
q=L1[k];
while(q!=0){
if (v[q->inf2]==0) dfs(q->inf2);
q=q->urm2;
}
nr++;
coada[nr]=k;
}
void dfs2(int k,int nrc){
nod *q;
cod *w;
v[k]=nrc;
q=L2[k];
w=new cod;
w->inf=k;
w->urm=sol[nrc];
sol[nrc]=w;
while(q!=0){
if (v[q->inf2]==0) dfs2(q->inf2,nrc);
q=q->urm2;
}
}
int main(){
citire();
for (i=1;i<=n;i++)
sol[i]=0;
for (i=1;i<=n;i++)
if (v[i]==0) dfs(i);
for (i=1;i<=n;i++)
v[i]=0;
for (i=n;i>=1;i--)
if (v[coada[i]]==0){
nrc++;
dfs2(coada[i],nrc);
}
fprintf(f2,"%d\n",nrc);
cod *w;
for (i=1;i<=nrc;i++){
w=sol[i];
while(w!=0){
fprintf(f2,"%d ",w->inf);
w=w->urm;
}
fprintf(f2,"\n");
}
fclose(f2);
return 0;
}