Cod sursa(job #2424755)

Utilizator IulianaRusuIuliana Rusu IulianaRusu Data 23 mai 2019 20:16:20
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int> graf[50005];
int grad[50005];
vector <int> coada;

void SortareTopologica(int N) {
    int i;
    for (i = 1; i <= N; i++)
        if (grad[i] == 0)
            coada.push_back(i);
    for (i = 0; i < N; i++) {
        int x = coada[i];
        int lim = graf[x].size();
        int j;
        for (j = 0; j < lim; j++) {
            grad[graf[x][j]]--;
            if (grad[graf[x][j]] == 0)
                coada.push_back(graf[x][j]);

        }
    }

}

int main() {

    int N, M, x, y;
    fin >> N >> M;
    int i;
    for (i = 0; i < M; i++) {
        fin >> x >> y;
        graf[x].push_back(y);
        grad[y]++;

    }
    SortareTopologica(N);
    for (i = 0; i < N; i++)
        fout << coada[i] << " ";
    return 0;
}