Pagini recente » Cod sursa (job #160347) | Istoria paginii runda/testere/clasament | Cod sursa (job #2967197) | Calibrare limite de timp | Cod sursa (job #1828077)
/**
*/
#include <cstdio>
#define maxn 50010
struct nod
{int v;nod* next;} *lv[maxn],*aux;
//am definit listele a.i. lv[x] = adresa de inceput a listei in care memoram vecinii lui x
int gr[maxn],q[maxn];
int main()
{
FILE *f=fopen("sortaret.in","r");
int n,m,i,x,y,pq,uq;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
//bag y in lista de vecini a lui x. Cel mai eficient este sa adaugam la inceput
//adik inainte de primul:
aux=new nod;
aux->v=y;
aux->next=lv[x];
lv[x]=aux;
//actualizez shi gradul intern al lui y:
gr[y]++;
}
//Incep coada cu nodurile care au gradul 0:
pq=1;uq=0;
for(i=1;i<=n;i++)if(!gr[i])q[++uq]=i;
//kt timp coada este nevida:
f=fopen("sortaret.out","w");
while(pq<=uq)
{
//afishez nodul curent:
fprintf(f,"%d ",q[pq]);
//procesez nodul pq: tuturor vecinilor sai le scad gradul cu 1
//daca in timpul acestui proces vreunul capata gradul 0 -> il bag in coada
for(aux=lv[q[pq]];aux;aux=aux->next)
{
gr[aux->v]--;
if(!gr[aux->v])q[++uq]=aux->v;
}
pq++;
}
return 0;
}