Cod sursa(job #1189181)

Utilizator xtreme77Patrick Sava xtreme77 Data 21 mai 2014 18:36:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>
#include <queue>
const int MAX = 50100;
using namespace std;
int grad[MAX];
vector <int> grf[MAX];
queue <int> coada;
int n,m;
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;--m){
        int x,y;
        scanf("%d%d",&x,&y);
        grf[x].push_back(y);
        grad[y]++;
    }
    for(int i=1;i<=n;++i)
        if(!grad[i])coada.push(i);
    vector <int> ::iterator it;
    while(!coada.empty()){
        int x=coada.front();
        for(it=grf[x].begin();it!=grf[x].end();++it){
            grad[*it]--;
            if(!grad[*it])coada.push(*it);
        }
        coada.pop();
        printf("%d ",x);
    }
    printf("\n");
    return 0;
}