Cod sursa(job #886930)

Utilizator toranagahVlad Badelita toranagah Data 23 februarie 2013 13:49:50
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

#define FORIT(it,v) for(typeof((v).begin())it=(v).begin();it!=(v).end();++it)
const int MAX_N = 50100;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int N, M;
vector<int> rules[MAX_N];
int req[MAX_N];

int main() {
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int p, q;
        fin >> p >> q;
        rules[p].push_back(q);
        ++req[q];
    }
    
    queue<int> free_nodes;
    for (int i = 1; i <= N; ++i) {
        if (req[i] == 0) free_nodes.push(i);
    }
    
    stack<int> output;
    while (!free_nodes.empty()) {
        int node = free_nodes.front();
        free_nodes.pop();
        output.push(node);
        
        FORIT (it, rules[node]) {
            if (--req[*it] == 0) {
                free_nodes.push(*it);
            }
        }
    }

    while (!output.empty()) {
        fout << output.top() << ' ';
        output.pop();
    }
    return 0;
}