Cod sursa(job #2968467)

Utilizator Emmy432622Rotariu Emanuel Emmy432622 Data 21 ianuarie 2023 09:48:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 5e4+5;
int n,m,a,b;
int grin[nmax];
vector<int>mch[nmax];
vector<int>sol;

int main()
{
    fin >> n >> m;
    for(int i = 1 ; i <= m ; ++i)
    {
        fin >> a >> b;
        grin[b]++;
        mch[a].push_back(b);
    }

    queue<int>q;
    for(int i = 1 ; i <= n ; ++i)
        if(grin[i]==0)
        {
            q.push(i);
            sol.push_back(i);
        }
    while(!q.empty())
    {
        int crt = q.front();
        for(auto it:mch[crt])
        {
            grin[it]--;
            if(!grin[it])
            {
                q.push(it);
                sol.push_back(it);
            }
        }
        q.pop();
    }

    for(auto it:sol)
        fout << it << ' ';

    return 0;
}