Cod sursa(job #2953257)

Utilizator Cosmin1605Damian Cosmin Cosmin1605 Data 10 decembrie 2022 19:52:59
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream input("sortaret.in");
ofstream output("sortaret.out");

vector<int> a[50001];
int grad[50001], viz[50001], coada[50001];

int main()
{
    int n, m, nod1, nod2;
    input >> n >> m;
    for(int i = 1; i <= m; i++){
        input >> nod1 >> nod2;
        a[nod1].push_back(nod2);
        grad[nod2]++;
    }

    int p = 1;
    int u = 0;
    for(int i = 1; i <= n; i++){
        if(viz[i] == 0 && grad[i] == 0){
            viz[i] = 1;
            u++;
            coada[u] = i;
        }
    }

    while(p <= u){
        int nod = coada[p];
        p++;
        for(int i = 0; i < a[nod].size(); i++){
            int nod2 = a[nod][i];
            grad[nod2]--;
            if(grad[nod2] == 0){
                u++;
                coada[u] = nod2;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        output << coada[i] << " ";
    }
    return 0;
}