Cod sursa(job #1377362)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 5 martie 2015 21:23:05
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <queue>

#define NMAX 50007

using namespace std;

queue < int > q;
vector < int > v[NMAX], Ans;
int Ap[NMAX];
int n, m;

void bfs(){
    while(!q.empty()){
        int Nod = q.front();
        q.pop();
        Ans.push_back(Nod);
        for(int i = 0; i < v[Nod].size(); ++i){
            --Ap[v[Nod][i]];
            if(Ap[v[Nod][i]] == 0)
                q.push(v[Nod][i]);
        }
    }
}

int main(){
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        ++Ap[b];
    }
    for(int i = 1; i <= n; ++i)
        if(Ap[i] == 0)
            q.push(i);
    bfs();
    for(int i = 0; i < n; ++i)
        printf("%d ", Ans[i]);
    return 0;
}