Cod sursa(job #3330711)

Utilizator ZsomborZsombor Horvay Zsombor Data 21 decembrie 2025 14:30:20
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream be("sortaret.in");
ofstream ki("sortaret.out");

int main()
{
    int n, m;
    be >> n >> m;

    vector<vector<int>> g(n + 1);

    for(int i = 0; i < m; i++)
    {
        int x, y;
        be >> x >> y;

        g[y].push_back(x);
    }

    queue<int> q;

    for(int i = 1; i <= n; i++)
    {
        if((int)g[i].size() == 0)
        {
            q.push(i);
            g[i].push_back(-1);
        }
    }

    vector<int> ans;

    while(!q.empty())
    {
        ans.push_back(q.front());

        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < (int)g[i].size(); j++)
            {
                if(g[i][j] == q.front())
                {
                    g[i].erase(g[i].begin() + j);
                    j--;
                }
            }

            if((int)g[i].size() == 0)
            {
                q.push(i);
                g[i].push_back(-1);
            }
        }

        q.pop();
    }

    for(int i : ans)
    {
        ki << i << " ";
    }
    
    return 0;
}