Cod sursa(job #2841143)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 29 ianuarie 2022 12:34:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int NMAX=50005;

int N, M, in[NMAX], sorted[NMAX], L;
vector<int> g[NMAX];
queue<int> q;

void Kahn()
{
    for(int i=1;i<=N;i++)
        if(in[i]==0)
            q.push(i);
    int nod;
    while(!q.empty()){
        nod=q.front();
        q.pop();
        sorted[++L]=nod;
        for(auto x: g[nod]){
            in[x]--;
            if(in[x]==0)
                q.push(x);
        }
    }
    for(int i=1;i<=L;i++)
        fout<<sorted[i]<<' ';
}

int main()
{
    fin>>N>>M;
    int x, y;
    for(int i=1;i<=M;i++){
        fin>>x>>y;
        g[x].push_back(y);
        in[y]++;
    }

    Kahn();

    fin.close();
    fout.close();
    return 0;
}