Pagini recente » Cod sursa (job #3155585) | Cod sursa (job #2414419) | Cod sursa (job #917063) | Cod sursa (job #2594732) | Cod sursa (job #3221835)
#include <stdio.h>
#include <stdlib.h>
#define N 50000
#define M 100000
typedef struct
{
int vf, urm;
} element;
element v[M+1];
int n, m, nv, lst[N+1], nrp[N+1], q[N+1];
void adauga(int x, int y)
{
///il adauga pe y in lista succesorilor lui x
nv++;
v[nv].vf = y;
v[nv].urm = lst[x];
lst[x] = nv;
}
int main()
{
FILE *in, *out;
in = fopen("sortaret.in", "r");
out = fopen("sortaret.out", "w");
fscanf(in, "%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int x, y;
fscanf(in, "%d%d", &x, &y);
adauga(x, y);
nrp[y]++;
}
int st = 0, dr = -1;
for (int i = 1; i <= n; i++)
{
if (nrp[i] == 0)///adaugam initial in coada varfurile fara predecesori
{
q[++dr] = i;
}
}
while (st <= dr)///cat timp q nu e vida
{
int x = q[st++];///il scoatem pe x din coada q
fprintf(out, "%d ", x);
for (int p = lst[x]; p != 0; p = v[p].urm)///parcurgem lista succesorilor lui x
{
int y = v[p].vf;
nrp[y]--;
if (nrp[y] == 0)
{
q[++dr] = y;///il adaugam pe y in coada
}
}
}
fclose(in);
fclose(out);
return 0;
}