Cod sursa(job #879874)

Utilizator Vlad.PPetcu Vlad Vlad.P Data 15 februarie 2013 22:38:00
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int pred[50001];
queue<int> q;
vector<int> succ[50001];
int rez[50001];
int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int n,r,t=0;
    scanf("%d%d",&n,&r);
    for(int i=1;i<=r;i++){
        int p,s;
        scanf("%d%d",&p,&s);
        ++pred[s];
        succ[p].push_back(s);
    }
    for(int i=1;i<=n;i++){
        if(pred[i]==0){
            q.push(i);
        }
    }
    while(q.empty()==false){
        for(int i=0;i<succ[q.front()].size();i++){
            --pred[succ[q.front()][i]];
            if(pred[succ[q.front()][i]]==0){
                q.push(succ[q.front()][i]);
            }
            rez[++t]=q.front();
            q.pop();
        }
    }
    for(int i=1;i<=t;i++){
        printf("%d ",rez[i]);
    }
    printf("\n");
    return 0;
}