Cod sursa(job #1565803)

Utilizator M.AndreiMuntea Andrei Marius M.Andrei Data 11 ianuarie 2016 14:13:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <queue>
using namespace std;

const int MAX = 50004;
int grad[MAX],n,m;
queue <int> coada[MAX]; queue <int> lista;

ofstream q("sortaret.out");

void read();
void sort();
void write();

int main()
{
    read();
    sort();
    return 0;
}

void sort()
{
    for (int i = 1; i <=n; i++)
    {
        if (grad[i] == 0)
        {
            lista.push(i);
        }
    }
    while (!lista.empty())
    {
        int x = lista.front();
        q<<x<<" ";
        lista.pop();
        while (!coada[x].empty())
        {
            int y = coada[x].front();
            coada[x].pop();
            grad[y]--;
            if (grad[y]==0)
            {
                lista.push(y);
            }
        }
    }
    q.close();

}


void read()
{
    ifstream f("sortaret.in");
    f>>n>>m;
    for ( ; m > 0; m--)
    {
        int x,y;
        f >> x >> y;
        coada[x].push(y);
        grad[y]++;
    }
    f.close();
}