Cod sursa(job #1522296)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 11 noiembrie 2015 15:54:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>
#define NMax 50005
using namespace std;

vector<int> G[NMax];

int N, M, i, j, k, Q[NMax], a, b, grad[NMax];

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

    scanf("%d %d\n",&N,&M);
    for(i=1;i<=M;i++)
    {
        scanf("%d %d\n",&a,&b);
        G[a].push_back(b);
        grad[b]++;
    }
    for(i=1;i<=N;i++)
        if(!grad[i])
            Q[++k]=i;
    for(i=1;i<=N;i++)
    {
        a=Q[i];
        for(vector<int>::iterator it=G[a].begin(); it!=G[a].end(); ++it)
        {
            grad[*it]--;
            if(!grad[*it])
                Q[++k]=*it;
        }
    }
    for(i=1;i<=k;i++)
        printf("%d ",Q[i]);

    return 0;
}