Cod sursa(job #1494520)

Utilizator DiClauDan Claudiu DiClau Data 1 octombrie 2015 12:16:33
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
using namespace std;
const int N = 50001, M = 100001;
int vf[N], lst[M], urm[M];
int nr = 0, coada[M], pre[N], inceput, sf;
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;
}