Cod sursa(job #999230)

Utilizator 2dorTudor Ciurca 2dor Data 19 septembrie 2013 18:15:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int MAXN = 50005;

int N, M, a, b;
int grad[MAXN];
vector <int> vecini[MAXN], coada;

void read() {
    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b;
        vecini[a].push_back(b);
        ++grad[b];//numarul de muchii care intra in nodul b
    }
}

void solve() {
    int i, node;
    vector <int>::iterator it;
    coada.push_back(0);
    for (i = 1; i <= N; ++i)
        if (grad[i] == 0)
            coada.push_back(i);
    i = 1;//la ce pozitie din coada suntem
    while (coada.size() <= (unsigned)N) {//cand am toate nodurile in coada, ma opresc
        node = coada[i++];
        for (it = vecini[node].begin(); it != vecini[node].end(); ++it) {
            --grad[*it];
            if (grad[*it] == 0)//nod devenit izolat
                coada.push_back(*it);
        }
    }
}

void write() {
    for (int i = 1; i <= N; ++i)
        fout << coada[i] << ' ';
    fout << '\n';
}

int main() {
    read();
    solve();
    write();
    fin.close();
    fout.close();
    return 0;
}