Cod sursa(job #876722)

Utilizator toranagahVlad Badelita toranagah Data 12 februarie 2013 00:56:56
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <list>
using namespace std;

const int MAX_N = 50100;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int N, M;
list<int> rules[MAX_N];
bool used[MAX_N];

int main() {
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int p, q;
        fin >> p >> q;
        rules[q].push_back(p);
    }

    bool go = true;
    while (go) {
        go = false;
        for (int i = 1; i <= N; ++i) {
            if (rules[i].empty() && !used[i]) {
                fout << i << ' ';
                used[i] = true;
                for (int j = 1; j <= N; ++j) {
                    if (i == j || rules[j].empty()) continue;
                    go = true;
                    list<int>::iterator it = find(rules[j].begin(), rules[j].end(), i);
                    if (it != rules[j].end()) rules[j].erase(it);
                }
            }
        }
    }
    return 0;
}