Pagini recente » Cod sursa (job #427123) | Cod sursa (job #961588) | Cod sursa (job #1926311) | Cod sursa (job #1050273) | Cod sursa (job #486713)
Cod sursa(job #486713)
#include<fstream>
using namespace std;
ifstream f("tc.in");
ofstream g("tc.out");
struct nod { int info;
nod* lg;
}*r,*vf[100001],*fv[100001],*af[100001];
int n,use[100001],temps,st[100001],nr;
void DF1(int i)
{ use[i]=1;
for(nod* p=vf[i];p;p=p->lg)if(!use[p->info])DF1(p->info);
st[++temps]=i;
}
void DF2(int i)
{ use[i]=1;
nod* p=af[nr];
p->info=i;
p->lg=af[nr];
af[nr]=p;
for(p=fv[i];p;p=p->lg)if(!use[p->info])DF2(p->info);
}
int main()
{ int i,m,a,b;
f>>n>>m;
for(i=1;i<=n;i++) vf[i]=0,fv[i]=0;
for(i=1;i<=m;i++) { f>>a>>b;
r=new nod;
r->info=b;
r->lg=vf[a];
vf[a]=r;
r=new nod;
r->info=a;
r->lg=fv[b];
fv[b]=r;
}
for(i=1;i<=n;i++)if(!use[i])DF1(i);
memset(use,0,sizeof(use));
for(i=n;i;i--)if(!use[st[i]]) { nr++;
DF2(st[i]);
}
g<<nr<<'\n';
for(;nr;nr--) { for(r=af[nr];r;r=r->lg)g<<r->info<<' ';
g<<'\n';
}
f.close();
g.close();
return 0;
}