Cod sursa(job #797293)

Utilizator Sm3USmeu Rares Sm3U Data 13 octombrie 2012 18:48:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <vector>
#include <queue>

#define nMax 50010

using namespace std;

int n;
vector <int> graf [nMax];
int grad [nMax];
queue <int> q;

void citire(){
    freopen ("sortaret.in", "r", stdin);
    scanf ("%d", &n);
    int m;
    scanf ("%d", &m);
    while (m --){
        int x;
        int y;
        scanf ("%d", &x);
        scanf ("%d", &y);
        graf[x].push_back (y);
        grad[y] ++;
    }
}

void afisare(){
    freopen ("sortaret.out", "w", stdout);
    for (int i = 1; i <= n; ++ i){
        if (grad[i] == 0){
            q.push(i);
            printf ("%d ", i);
        }
    }
    while (!q.empty()){
        int x = q.front();
        q.pop();
        for (unsigned int i = 0; i < graf[x].size(); ++ i){
            grad[graf[x][i]] --;
            if (grad[graf[x][i]] == 0){
                q.push (graf[x][i]);
                printf ("%d ", graf[x][i]);
            }
        }
    }
}


int main()
{
    citire();
    afisare();

    return 0;
}