Cod sursa(job #3250866)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 23 octombrie 2024 21:48:04
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m, i, x, y, grad[50005], r[50005], k;
queue<int>s;
set<int>v[50005];
int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++) {
        fin>>x>>y;
        v[x].insert(y);
    }
    for (i=1; i<=n; i++) {
        for (auto j:v[i]) grad[j]++;
    }
    for (i=1; i<=n; i++) if (grad[i]==0) s.push(i);
    while (!s.empty()) {
        x=s.front();
        s.pop();
        for (auto i:v[x]) {
            grad[i]--;
            if (grad[i]==0) s.push(i);
        }
        r[++k]=x;
    }
    for (i=1; i<=n; i++) fout<<r[i]<<' ';
    return 0;
}