Pagini recente » Cod sursa (job #610048) | Cod sursa (job #2212062) | Cod sursa (job #2650068) | Istoria paginii utilizator/andi.georgescu | Cod sursa (job #1494518)
#include<stdio.h>
using namespace std;
const int N = 50001, M = 100001;
int vf[N], lst[M], urm[M];
int nr = 0, coada[N], pre[N], inceput, sf, rad[N];
bool viz[N];
void adauga(int x, int y)
{
nr++;
vf[nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
void bfs(int x0)
{
int p, y;
while (inceput < sf)
{
p = lst[coada[inceput]];
x0 = coada[inceput];
while (p != 0)
{
y = vf[p];
pre[y]--;
if (pre[y] == 0)
coada[sf++] = y;
p = urm[p];
}
inceput++;
}
}
int main ()
{
FILE *in, *out;
in = fopen ("sortaret.in", "r");
out = fopen ("sortaret.out", "w");
int n, m, c = 0;
fscanf (in, "%d%d", &n, &m);
int i, x, y;
for (i = 1; i <= m; i++)
{
fscanf (in, "%d%d", &x, &y);
adauga(x, y);
pre[y]++;
}
int start;
for (i = 1; i <= n; i++)
if (pre[i] == 0)
{
start = i;
coada[sf++] = i;
}
bfs(start);
for (i = 0; i < sf; i++)
fprintf (out, "%d ", coada[i]);
return 0;
}