Cod sursa(job #3312099)

Utilizator Victor5539Tanase Victor Victor5539 Data 26 septembrie 2025 09:50:19
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

const int MAX=50000;
int n,m,x,y,deg[MAX+5],i;
queue <int> q;
vector <int> edge[MAX+5],sol;
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);

    fin>>n>>m;

    while (m--)
    {
        fin>>x>>y;
        edge[x].push_back(y);
        deg[y]++;
    }

    for (i=1; i<=n; i++)
        if (deg[i]==0)
        {
            sol.push_back(i);
            q.push(i);
        }

    while (!q.empty())
    {
        int node=q.front();
        q.pop();

        for (auto x: edge[node])
        {
            deg[x]--;
            if (deg[x]==0)
            {
                q.push(x);
                sol.push_back(x);
            }
        }
    }

    for (auto x: sol)
        fout<<x<<" ";
    return 0;
}