Cod sursa(job #2659379)

Utilizator UtilizatorGBGeorge Bodea UtilizatorGB Data 16 octombrie 2020 18:12:59
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define MX 50001

int n, m;
vector<int> graf[MX];
int grade[MX];
int vizitate[MX];
queue<int> coada;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

void sortTop(int n) {

    while (coada.empty() == 0) {
        int primul = coada.front();
        vizitate[primul] = 1;

        for (int i = 0; i < graf[primul].size(); i++) {
            int element = graf[primul][i];
            grade[element]--;
            if (grade[element] == 0)
                coada.push(element);
        }

        g<<primul<<' ';
        coada.pop();
    }
}

void SortareTopologica(int n) {

    for (int i = 1; i <= n; i++)
        if (grade[i] == 0)
            coada.push(i);

    sortTop(n);
}

int main()
{
    f>>n>>m;

    for (int i = 0; i < m; i++) {
        int sursa, destinatie;
        f>>sursa>>destinatie;
        graf[sursa].push_back(destinatie);
        grade[destinatie]++;
    }
    int tar = 0;
    SortareTopologica(n);

    return 0;
}