Cod sursa(job #1434869)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 11 mai 2015 16:29:43
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <utility>
#include <queue>

using namespace std;

int dg_minus[50005], coada[50005];

int main()
{
    fstream f("sortaret.in");
    ofstream g("sortaret.out");

    int nr_noduri, nr_muchii, nod_plecare, nod_destinatie, nod_aux;

    vector< int > graf[50005];

    f >> nr_noduri >> nr_muchii;

    for(int i = 0; i < nr_muchii; i++)
        {
            f >> nod_plecare >> nod_destinatie;
            dg_minus[nod_destinatie]++;
            graf[nod_plecare].push_back(nod_destinatie);
        }

    for(int i = 1; i <= nr_noduri; i++)
        if(dg_minus[i] == 0)
            coada[++coada[0]] = i;

    for(int i = 1; i <= nr_noduri; i++)
        {
            nod_aux = coada[i];

            for(unsigned int j = 0; j < graf[nod_aux].size(); j++)
                {
                    dg_minus[graf[nod_aux][j]]--;
                    if(dg_minus[graf[nod_aux][j]] == 0)
                        coada[++coada[0]] = graf[nod_aux][j];
                }
        }

    for(int i = 1; i <= coada[0]; i++)
        g << coada[i] << " ";

    return 0;
}