Pagini recente » Cod sursa (job #627277) | Cod sursa (job #2719467) | Cod sursa (job #2206060) | Cod sursa (job #1937913) | Cod sursa (job #270550)
Cod sursa(job #270550)
#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];
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(i=1;i<=n;i++)
if(u[i]==x)
fout<<i<<' ';
fout<<'\n';
}
fout.close();
return 0;
}
void df2(int nod)
{
lista *p;
u[nod]=nr;
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;
}