Cod sursa(job #886933)

Utilizator toranagahVlad Badelita toranagah Data 23 februarie 2013 13:51:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
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);
    }
    
    while (!free_nodes.empty()) {
        int node = free_nodes.front();
        free_nodes.pop();
        fout << node << ' ';
        
        FORIT (it, rules[node]) {
            if (--req[*it] == 0) {
                free_nodes.push(*it);
            }
        }
    }
    return 0;
}