Pagini recente » Cod sursa (job #687199) | Cod sursa (job #688393) | Cod sursa (job #3249053) | Cod sursa (job #752160) | Cod sursa (job #270557)
Cod sursa(job #270557)
#include<fstream.h>
#define xn 100001
#define xm 200001
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int u[xn],n,m,st[xn],nr;
struct lista {int nod; lista *urm; } *g[xn],*gt[xn],*l[xn];
void df1(int nod);
void df2(int nod);
int main()
{
int i,x,y;
lista *p;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
p=new lista;
p->nod=y; p->urm=g[x]; g[x]=p;
p=new lista;
p->nod=x; p->urm=gt[y]; gt[y]=p;
}
for(i=1;i<=n;i++)
if(!u[i])
df1(i);
memset(u,0,sizeof(u));
for(i=n;i>0;i--)
if(!u[st[i]])
nr++,df2(st[i]);
fout<<nr<<'\n';
for(x=1;x<=nr;x++)
{
for(p=l[x];p;p=p->urm)
fout<<p->nod<<' ';
fout<<'\n';
}
fout.close();
return 0;
}
void df2(int nod)
{
lista *p;
u[nod]=1;
p=new lista;
p->nod=nod;
p->urm=l[nr];
l[nr]=p;
for(p=gt[nod];p;p=p->urm)
if(!u[p->nod])
df2(p->nod);
}
void df1(int nod)
{
lista *p;
u[nod]=1;
for(p=g[nod];p;p=p->urm)
if(!u[p->nod])
df1(p->nod);
st[++st[0]]=nod;
}