Cod sursa(job #1464498)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 23 iulie 2015 18:07:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int> graf[50010];
int coada[50010],grad_exterior[50010];
int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int n,m,i,j,a,b,nod,dim;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        graf[a].push_back(b);
        grad_exterior[b]++;
    }
    for(i=1;i<=n;i++)
        if(grad_exterior[i]==0){
            coada[0]++;
            coada[coada[0]]=i;
        }
    for(i=1;i<=n;i++){
        nod=coada[i];
        dim=graf[nod].size();
        for(j=0;j<dim;j++){
            grad_exterior[graf[nod][j]]--;
            if(grad_exterior[graf[nod][j]]==0){
                coada[0]++;
                coada[coada[0]]=graf[nod][j];
            }
        }
    }
    for(i=1;i<=n;i++)
        printf("%d ",coada[i]);
    return 0;
}