Pagini recente » Cod sursa (job #3216009) | Cod sursa (job #474867) | Cod sursa (job #1300625) | Cod sursa (job #1527670) | Cod sursa (job #255327)
Cod sursa(job #255327)
#include<fstream.h>
#define fis1 "ctc.in"
#define fis2 "ctc.out"
#define nmax 100001
#define mmax 200001
ifstream f(fis1);
ofstream g(fis2);
struct lista
{
long inf;lista *urm;}*a[nmax],*at[nmax],*c[nmax];
long n,m,v[nmax],nr;
void read()
{
f>>n>>m;
for(long i=1;i<=m;i++)
{
long x,y;
f>>x>>y;
lista *p=new lista;
p->inf=y;p->urm=a[x];
a[x]=p;
p=new lista;
p->inf=x;p->urm=at[y];
at[y]=p;
}
f.close();
}
void df1(long x)
{
v[x]=-1;
for(lista *p=a[x];p;p=p->urm)
if(v[p->inf]==0)df1(p->inf);
}
void df2(long x,long nr)
{
v[x]=nr; lista *q=new lista;
q->inf=x;q->urm=c[nr];c[nr]=q;
for(lista *p=at[x];p;p=p->urm)
if(v[p->inf]==-1)df2(p->inf,nr);
}
void write()
{
g<<nr<<'\n';
for(long i=1;i<=nr;i++)
{
for(lista *p=c[i];p;p=p->urm)
g<<p->inf<<' ';
g<<'\n';
}
g.close();
}
/*void print(lista *a[])
{
for(long i=1;i<=n;i++)
{
for(lista* p=a[i];p;p=p->urm)
cout<<p->inf<<" ";
cout<<'\n';
}
cout<<"***********\n";
} */
int main()
{
read();
/*print(a);print(at);*/
for(long i=1;i<=n;i++)
{
if(v[i]==0)
{
nr++;
df1(i);
df2(i,nr);
for(long j=1;j<=n;j++)
if(v[j]==-1)v[j]=0;
}
}
write();
return 0;
}