Cod sursa(job #1997358)

Utilizator roitainNiculae Cristian roitain Data 4 iulie 2017 00:03:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<cstdio>
#include<queue>

using namespace std;

struct node{
    int val;
    node *urm;
}*nodes[50001];

int ex[50001];
int in[50001];
int N,M;
int i;
int a,b;
node *p;

queue<int> q;
int main(){

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

    scanf("%d %d",&N,&M);

    for(i = 0; i < M; ++i){
        scanf("%d %d",&a,&b);
        p = new node;
        p->val = b;
        p->urm = nodes[a];
        nodes[a] = p;
        ++ex[b];
        ++in[a];
    }

    for(i = 1; i <= N; ++i){
        if(ex[i]==0)
            q.push(i);
    }

    int current;

    while(!q.empty()){
        current = q.front();
        q.pop();
        printf("%d ",current);
        p = nodes[current];
        while(p != NULL){
            if(--ex[p->val] == 0)
                q.push(p->val);
            p = p->urm;
        }
    };

    return 0;
}