Cod sursa(job #2147242)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 28 februarie 2018 16:27:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>

#define N 50002
#define M 100002
using namespace std;

int n, m, k, v[2][M], start[N], pred[N];

void eliminare(int nod)
{
    int w=start[nod];
    while(w)
    {
        pred[v[0][w]]--;
        w=v[1][w];
    }
    start[nod]=0;
    pred[nod]=-1;
}

int main()
{
    int i,j;

    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d%d", &n, &m);
    while(m)
    {
        scanf("%d%d", &i, &j);
        k++;
        v[0][k]=j;
        v[1][k]=start[i];
        start[i]=k;
        pred[j]++;
        m--;
    }
    bool ok=1;
    while(ok)
    {
        ok=0;
        for(int i=1; i<=n; i++)
        {
            if(!pred[i])
            {
                eliminare(i);
                printf("%d ", i);
                ok=1;
            }
        }
    }
    return 0;
}