Cod sursa(job #1061796)

Utilizator RarRaresNedelcu Rares RarRares Data 20 decembrie 2013 12:10:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define nmax 50005

using namespace std;

int n, m;
vector<int> graf[nmax];
queue<int> coada;
int grad_int[nmax];

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d %d\n", &x, &y);

        graf[x].push_back(y);
        grad_int[y]++;
    }
}




void sortaret()
{
    for(int i = 1; i <= n; i++)
        if(grad_int[i] == 0)
            coada.push(i);

    while(!coada.empty())
    {
        int x = coada.front();
        coada.pop();
        cout << x << ' ';
        for(vector<int>::iterator it = graf[x].begin(); it != graf[x].end(); ++it)
        {
            grad_int[*it]--;
            if(grad_int[*it] == 0)
                coada.push(*it);
        }
    }
}
int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    citire();
    sortaret();

    return 0;
}