Cod sursa(job #3269284)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 18 ianuarie 2025 15:59:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 5e4 + 1;
int N, M;
int sorted[N_MAX];
int gradExt[N_MAX];

vector<int> G[N_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> M;

    for(int i = 0, x, y; i < M; i++)
    {
        cin >> x >> y;

        G[x].push_back(y);
        gradExt[y]++;
    }
}

void Solve()
{
    int k = 0;
    for(int i = 1; i <= N; i++)
        if(gradExt[i] == 0)
            sorted[++k] = i;

    for(int i = 1, nod; i <= N; i++)
    {
        nod = sorted[i];
        for(int fiu : G[nod])
        {
            gradExt[fiu]--;
            if(gradExt[fiu] == 0)
                sorted[++k] = fiu;
        }
    }

    for(int i = 1; i <= N; i++)
        cout << sorted[i] << ' ';
    cout << '\n';
}

int main()
{
    SetInput("sortaret");

    ReadInput();
    Solve();

    return 0;
}