Cod sursa(job #2922087)

Utilizator RaresPoinaruPoinaru-Rares-Aurel RaresPoinaru Data 3 septembrie 2022 20:41:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

const int MAXN=100010;

int n,m,f[MAXN];
vector <int> g[MAXN];
deque <int> dq;

int main()
{
    fin >>n>>m;
    for (int i=1;i<=m;++i){
        int x,y;
        fin >>x>>y;
        f[y]++;
        g[x].push_back (y);
    }
    for (int i=1;i<=n;++i){
        if (f[i]==0){
            dq.push_back (i);
        }
    }
    while (dq.empty ()==false){
        int aux=dq.front ();
        dq.pop_front ();
        for (int i=0;i<g[aux].size ();++i){
            if (f[g[aux][i]]==1)
                dq.push_back (g[aux][i]);
            f[g[aux][i]]--;
        }
        fout <<aux<<' ';
    }
    fin.close ();
    fout.close ();
    return 0;
}