Cod sursa(job #1492179)

Utilizator UMihneaUngureanu Mihnea UMihnea Data 27 septembrie 2015 10:54:05
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <vector>
using namespace std;
vector<int> v[50010];

int i, n, m, b, t, x, y, c[50010], g[50010];

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

    scanf("%d%d",&n,&m);

    for(;m;m--)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        g[y]++;
    }

    t = 0; b = 1;
    for(i=1;i<=n;i++)
        if(!g[i])
            c[++t] = i;

    for(;b<=n;b++)
        for(auto vec:v[c[b]])
        {
            g[vec]--;
            if(!g[vec])
                c[++t] = vec;
        }

    for(i=1;i<=n;i++)
        printf("%d ",c[i]);

    return 0;
}