Cod sursa(job #1039477)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 23 noiembrie 2013 09:23:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <queue>
#define every(it, C) vector<int>::iterator it = C.begin(); it != C.end(); it++
#define range(i, a, b) int i = (a); i <= (b); i++
#define nmax 50000+5
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int> graf[nmax];
int incidenta[nmax];
queue<int> coada;
vector<int> solutie;
int n;

void citire()
{
    int m;
    int x, y;
    fin >> n >> m;
    for(range(i, 1, m))
    {
        fin >> x >> y;
        graf[x].push_back(y);
        incidenta[y]++;
    }
}

void sortareTopologica()
{
    int curent;
    for(range(i, 1, n))
        if (incidenta[i] == 0)
            coada.push(i);
    while (!coada.empty())
    {
        curent = coada.front();
        coada.pop();

        for(every(it, graf[curent]))
            if (incidenta[*it] > 0)
            {
                incidenta[*it]--;
                if (incidenta[*it] == 0)
                    coada.push(*it);
            }

        solutie.push_back(curent);
    }
}

void afisare()
{
    for(every(it, solutie))
        fout << *it << ' ';
    fout << '\n';
}
int main()
{
    citire();
    sortareTopologica();
    afisare();
    return 0;
}