Cod sursa(job #1471148)

Utilizator sabin.antoheSabin Antohe sabin.antohe Data 13 august 2015 11:55:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
using namespace std;

#define MAXN 50100
int grad[MAXN], coada[MAXN], N, M;
vector <int> map[MAXN];

int main(void) {
    ifstream input("sortaret.in");
    ofstream output("sortaret.out");
    input >> N >> M;
    for(int i = 1, x, y; i <= M; i++) {
        input >> x >> y;
        map[x].push_back(y);
        grad[y]++;
    }

    for(int i = 1; i  <= N; i++)
        if(grad[i] == 0)
            coada[++coada[0]] = i;

    vector<int>::iterator it;
    for(int i = 1, ok; i <= N; i++) {
        ok = coada[i];
        for(it = map[ok].begin(); it != map[ok].end(); it++) {
            grad[*it]--;
            if(grad[*it] == 0)
                coada[++coada[0]] = *it;
        }
    }
    for(int i = 1; i <= N; i++)
        output << coada[i] << " ";
    return 0;
}