Cod sursa(job #1434854)

Utilizator adi_ispas95FMI - Adrian Ispas adi_ispas95 Data 11 mai 2015 16:09:12
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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 i, j;
    int nr_noduri, nr_muchii, nod_plecare, nod_destinatie, pondere, nod_aux;

    vector<pair<int,int> > graf[50005];
    pair<int,int> pereche;

    f >> nr_noduri >> nr_muchii;

    for(i = 0; i < nr_muchii; i++)
        {
            f >> nod_plecare >> nod_destinatie;
            dg_minus[nod_destinatie]++;

            pereche = make_pair(nod_destinatie,pondere);
            graf[nod_plecare].push_back(pereche);
        }

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

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

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

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

    return 0;
}