Pagini recente » Istoria paginii runda/gonathan/clasament | Cod sursa (job #2783614) | Cod sursa (job #2893679) | Cod sursa (job #1689971) | Cod sursa (job #796591)
Cod sursa(job #796591)
#include<stdio.h>
#define nmax 100005
#define mmax 200005
struct muchie{long x, y;};
long n, m, i, poz, tac, comp, j;
long rez[nmax], gr[nmax], pozinc[nmax], pozac[nmax], pozinct[nmax], pozact[nmax], ma[mmax], mat[mmax], viz[nmax], vf[nmax], grt[nmax];
muchie v[nmax];
void citire()
{
scanf("%ld %ld",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%ld %ld",&v[i].x,&v[i].y);
gr[v[i].x]++; grt[v[i].y]++;
}
pozinc[1]=pozac[1]=1; pozinct[1]=pozact[1]=1;
for (i=2;i<=n;i++)
{
pozinc[i]=pozinc[i-1]+gr[i-1]; pozac[i]=pozinc[i];
pozinct[i]=pozinct[i-1]+grt[i-1]; pozact[i]=pozinct[i];
}
for (i=1;i<=m;i++)
{
ma[pozac[v[i].x]]=v[i].y; pozac[v[i].x]++;
mat[pozact[v[i].y]]=v[i].x; pozact[v[i].y]++;
}
}
void dfs1(long nod)
{
long i;
viz[nod]=1;
for (i=pozinc[nod];i<=pozinc[nod]+gr[nod]-1;i++)
if (viz[ma[i]]==0)
dfs1(ma[i]);
vf[++tac]=nod;
}
void dfs2(long nod)
{
long i;
viz[nod]=2;
for (i=pozinct[nod];i<=pozinct[nod]+grt[nod]-1;i++)
if (viz[mat[i]]<2)
dfs2(mat[i]);
rez[++poz]=nod;
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
for (i=1;i<=n;i++)
if (!viz[i])
dfs1(i);
for (i=n;i>=1;i--)
if (viz[vf[i]]<2)
{
comp++;
dfs2(vf[i]);
poz++;
}
printf("%ld\n",comp);
poz=1;
for (i=1;i<=comp;i++)
{
while (rez[poz]!=0)
{ printf("%ld ",rez[poz]); poz++; }
poz++;
printf("\n");
}
return 0;
}