Cod sursa(job #1236859)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 2 octombrie 2014 18:32:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <vector>
#include <queue>

#define NMAX 50005

using namespace std;

int N, M, grad_exterior[NMAX], grad_interior[NMAX];
vector <int> G[NMAX];
queue <int> coada;

void citire()
{
    int x, y;

    scanf("%d %d", &N, &M);

    for (int i = 1; i <= M; ++i)
    {
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        grad_exterior[x]++;
        grad_interior[y]++;
    }

    for (int i = 1; i <= N; ++i)
        if (grad_interior[i] == 0)
        {
            grad_interior[i] = -1;
            coada.push(i);
        }
}

void rezolvare(int nod)
{
    for (int i = 0; i < grad_exterior[nod]; ++i)
    {
        if (grad_interior[G[nod][i]] > 0)
            grad_interior[G[nod][i]]--;
        if (grad_interior[G[nod][i]] == 0)
        {
            coada.push(G[nod][i]);
            grad_interior[G[nod][i]] = -1;
        }
    }
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    citire();
    while (!coada.empty())
    {
        printf("%d ", coada.front());
        rezolvare(coada.front());
        coada.pop();
    }

    return 0;
}