Pagini recente » Cod sursa (job #2352992) | Cod sursa (job #1522869) | Cod sursa (job #334987) | Cod sursa (job #1503889) | Cod sursa (job #353138)
Cod sursa(job #353138)
#include<stdio.h>
#define nmax 100010
long n,m,nr;
long s[nmax],v[nmax];
struct nod
{
long info;
nod *urm;
};
nod *g[nmax],*t[nmax],*c[nmax];
void InsertBegin(long a,long b)
{
nod *aux;
aux=new nod;
aux->info=b;
aux->urm=g[a];
g[a]=aux;
aux=new nod;
aux->info=a;
aux->urm=t[b];
t[b]=aux;
}
void read()
{
long i,a,b;
scanf("%ld%ld",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%ld%ld",&a,&b);
InsertBegin(a,b);
}
}
void dfs(long i)
{
nod *p;
v[i]=1;
for (p=g[i];p;p=p->urm)
{
if (!v[p->info])
{
dfs(p->info);
s[++s[0]]=p->info;
}
}
}
void dfst(long i)
{
nod *p,*aux;
v[i]=0;
aux=new nod;
aux->info=i;
aux->urm=c[nr];
c[nr]=aux;
for (p=t[i];p;p=p->urm)
{
if (v[p->info])
{
dfst(p->info);
}
}
}
void print()
{
printf("%ld\n",nr);
long i;
nod *p;
for (i=1;i<=nr;i++)
{
for (p=c[i];p;p=p->urm)
printf("%ld ",p->info);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read();
long i;
for (i=1;i<=n;i++)
{
if (!v[i])
{
dfs(i);
s[++s[0]]=i;
}
}
for (i=n;i>=1;i--)
{
if (v[s[i]])
{
nr++;
dfst(s[i]);
}
}
print();
return 0;
}