Cod sursa(job #3242872)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 14 septembrie 2024 13:14:27
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 5e4 + 1;

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

int n, m, gr[NMAX];
vector<int> G[NMAX], sol;
queue<int> q;

void citire()
{
    int x, y;
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y;
        G[x].push_back(y);
        ++gr[y];
    }
}

void solutie()
{
    for(int i = 1; i <= n; ++i)
        if(!gr[i])
            q.push(i);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        sol.push_back(x);
        for(const auto &y : G[x])
        {
            if(!(--gr[y]))
                q.push(y);
        }
    }
}

void afisare()
{
    for(const auto &x : sol)
        fout << x << ' ';
}

int main()
{
    citire();
    solutie();
    afisare();
    return 0;
}