Cod sursa(job #2569060)

Utilizator ioana_marinescuMarinescu Ioana ioana_marinescu Data 4 martie 2020 10:57:34
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 50000;

int n, m;
int grad[MAX_N + 5];

vector<int> G[MAX_N + 5], ans;
queue<int> q;

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++){
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        grad[y]++;
    }

    for (int i = 1; i <= n; i++)
        if (grad[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int u = q.front();
        ans.push_back(u);
        q.pop();

        for (int v : G[u]){
            grad[v]--;
            if (grad[v] == 0)
                q.push(v);
        }
    }

    for (int i : ans)
        fout << i << ' ';
    return 0;
}