Pagini recente » Cod sursa (job #608219) | Cod sursa (job #2299265) | Profil ariba021 | Cod sursa (job #3264898) | Cod sursa (job #694298)
Cod sursa(job #694298)
#include <cstdio>
using namespace std;
FILE *in=fopen("ctc.in","r");
FILE *out=fopen("ctc.out","w");
struct nod {int dest;nod *leg;};
nod *a[10000],*t[10000],*p;
int n,m,i,j,x,y,stack[10000],top,end,ord,mark[10000],sign[10000];
void adees(int k)
{mark[k]=i;
nod *point;
point=a[k];
while (point!=NULL)
{if (mark[point->dest]==0)
adees(point->dest);
point=point->leg;
}
stack[++top]=k;
}
void tdfs(int k)
{sign[k]=ord;
nod *point;
point=t[k];
while (point!=NULL)
{if (sign[point->dest]==0)
tdfs(point->dest);
point=point->leg;
}
}
int main()
{fscanf(in,"%d %d",&n,&m);
for (i=1;i<=n;i++){a[i]=NULL;t[i]=NULL;}
for (i=1;i<=m;i++)
{fscanf(in,"%d %d",&x,&y);
p=new(nod);
p->dest=y;
p->leg=a[x];
a[x]=p;
p=new(nod);
p->dest=x;
p->leg=t[y];
t[y]=p;
}
//end reading
top=0;i=1;
while(top<n)
{
if (mark[i]==0)
adees(i);
i++;
}
ord=0;
for (i=top;i>=1;i--)
if (sign[stack[i]]==0){ord++;
tdfs(stack[i]);}
for (i=1;i<=n;i++)
{fprintf(out,"%d ",i);
if ((mark[i]!=mark[i+1])or(sign[i]!=sign[i+1])) fprintf(out,"%c",'\n');
}
fclose(in);fclose(out);
return 0;
}