Pagini recente » Cod sursa (job #2077252) | Cod sursa (job #458439) | Cod sursa (job #2684611) | Cod sursa (job #1550148) | Cod sursa (job #149844)
Cod sursa(job #149844)
#include <stdio.h>
struct lista
{int st,dr;
lista *next;
};
lista *prim=new lista,*ultim=new lista,*temp;
int v[100001],n,m,a[100001];
int citire()
{FILE *f;
int x,y;
f=fopen("sortaret.in","r");
fscanf(f,"%d %d",&n,&m);
fscanf(f,"%d %d",&x,&y);
v[y]++;
prim->st=x;
prim->dr=y;
prim->next=NULL;
ultim=prim;
for (int i=2;i<=m;i++)
{fscanf(f,"%d %d",&x,&y);
v[y]++;
temp=new lista;
temp->st=x;
temp->dr=y;
temp->next=NULL;
ultim->next=temp;
ultim=temp;
}
fclose(f);
return 0;
}
int sortare_topologica()
{FILE *f;
int i,k=1,q;
lista *t=new lista;
f=fopen("sortaret.out","w");
for (i=1;i<=n;i++) a[i]=v[i];
while (k==1)
{
k=0;
for (i=1;i<=n;i++)
if (v[i]==0) {fprintf(f,"%d ",i);k=1;v[i]=-1;}
temp=prim;t=temp;
while (temp!=NULL)
{q=0;
if (v[temp->st]==-1) // stergem nodul temp
{q=1;
a[temp->dr]--;
if (temp==prim) {prim=temp->next;
//delete(temp);
//temp=new lista;
temp=prim;
t=prim;
}
else {t->next=temp->next;
//delete(temp);
//temp=new lista;
temp=t;
}
}
if (q==0) {if (t!=temp) t=t->next;
temp=temp->next;
}
}
for (i=1;i<=n;i++) if (v[i]!=-1) v[i]=a[i];
}
fclose(f);
return 0;
}
int main()
{int i;
for (i=1;i<=n;i++) v[i]=0;
citire();
sortare_topologica();
/*
temp=prim;
while (temp!=NULL)
{printf("%d %d\n",temp->st,temp->dr);
temp=temp->next;
}
getch(); */
return 0;
}