Cod sursa(job #1434876)

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

using namespace std;

int dg_minus[50100], coada[50100];
int nr_noduri, nr_muchii;
vector< int > graf[50005];

void read()
{
    fstream f("sortaret.in");
    ofstream g("sortaret.out");

    f >> nr_noduri >> nr_muchii;

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

}

void topoligic()
{
     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++)
        {
            int 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];
                }
        }
}

void write()
{
    ofstream g("sortaret.out");
    for(int i = 1; i <= coada[0]; i++)
        g << coada[i] << ' ';
}

int main()
{
    read();
    topoligic();
    write();
    return 0;
}