Cod sursa(job #2529441)

Utilizator mihneazarojanuMihnea Bogdan Zarojanu mihneazarojanu Data 23 ianuarie 2020 15:25:03
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N = 50000, M = 100000;
int n, vf[M], urm[M], lst[M], nr, cnt[N + 1], q[N + 1], st, dr = -1;

void adaug(int x, int y){
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
    cnt[y]++;
}

void citire(){
    ifstream in("sortaret.in");
    int m;
    in >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        in >> x >> y;
        adaug(x, y);
    }
    in.close();
}

void sortare(){
    for(int i = 1; i <= n; i++){
        if(cnt[i] == 0){
            q[++dr] = i;
        }
    }
    ofstream out("sortaret.out");
    while(st <= dr){
        int x = q[st++];
        out << x << ' ';
        for(int p = lst[x]; p != 0; p = urm[p]){
            int y = vf[p];
            cnt[y]--;
            if(cnt[y] == 0){
                q[++dr] = y;
            }
        }
    }
    out.close();
}

int main(){
    citire();
    sortare();
    return 0;
}