Cod sursa(job #2570863)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 4 martie 2020 19:42:58
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

const int MAX = 5e4 + 5;

int n, m;
int grad[MAX];

vector<int> G[MAX], ans;
queue<int> q;

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        f >> 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)
        g << i << " ";
    return 0;
}