Pagini recente » Cod sursa (job #38586) | Cod sursa (job #417140) | Cod sursa (job #1879780) | Cod sursa (job #369899) | Cod sursa (job #144162)
Cod sursa(job #144162)
/*
Se dau N activitati si M reguli de forma (i,j) cu semnificatia activitatea i precede activitatea j. Sa se stabileasca
o ordine de indeplinire a activitatilor astfel incat sa fie respectate regulile date. Se considera graful activitatilor
ca fiind aciclic.
Complexitate: O(M+N)
*/
#include <stdio.h>
#define infile "sortaret.in"
#define outfile "sortaret.out"
#define NMAX 5005
struct NOD{int x; NOD *adr;};
FILE *fin,*fout;
NOD *prim[NMAX];
int timpfinal[NMAX],timp;
int n,m;
int ordine[NMAX];
short int vizitat[NMAX];
inline void adaug_st(NOD *(&prim), int x)
{NOD *a=new NOD;
a->x=x;
a->adr=prim;
prim=a;}
void citire()
{
int i,u,v;
fin=fopen(infile,"r");
fscanf(fin,"%d %d",&n,&m);
for(i=0;i<n;i++)
prim[i]=NULL;
for(i=0;i<m;i++)
{fscanf(fin,"%d %d",&u,&v);
adaug_st(prim[u-1],v-1);}
fclose(fin);
}
void df(int varf)
{
NOD *b=prim[varf];
while(b)
{if(!vizitat[b->x])
{vizitat[b->x]=1;
df(b->x);
timp++;}
b=b->adr;}
timpfinal[varf]=timp;
}
void scriere()
{
fout=fopen(outfile,"w");
for(int i=0;i<n;i++)
fprintf(fout,"%d ",ordine[i]+1);
fclose(fout);
}
int main()
{
int i;
citire();
timp=0;
for(i=0;i<n;i++)
vizitat[i]=0;
for(i=0;i<n;i++)
if(!vizitat[i])
{vizitat[i]=1;
df(i);
timp++;}
for(i=0;i<n;i++)
ordine[n-1-timpfinal[i]]=i;
scriere();
return 0;
}