Cod sursa(job #2778508)

Utilizator andutzu999Andy Blanaru andutzu999 Data 1 octombrie 2021 15:59:42
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
using namespace std;

int main() {

    int N, M;

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

    fin >> N >> M;
    vector<int> vect[N+1];
    vector<int> grades(N+1, 0);
    queue<int> q;

    int a, b;
    for (int i = 1; i <= M; i++) {
        fin >> a >> b;
        vect[a].push_back(b);
        grades[b]++;
    }

    for (int i = 1; i <= N; i++) {
        if (grades[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int p = q.front();
        q.pop();
        for (int j = 0; j < vect[p].size(); j++) {
            grades[vect[p][j]]--;

            if (grades[vect[p][j]] == 0) {
                q.push(vect[p][j]);
            }
        }
        fout << p << " ";
    }

    return 0;
}