Cod sursa(job #269404)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 2 martie 2009 20:58:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
#include<vector>

#define N 50002

using namespace std;

vector<int> a[N];
int q[N], n, grad[N];

void citire(), rezolva();

int main (){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    citire();
    rezolva();
int i;
    for (i = 1; i <= n; i++)
        printf("%d ", q[i]);
    printf("\n");
    return 0;
}

void citire(){
int m, x, y;
    scanf("%d %d", &n, &m);
    for (; m; m--){
        scanf("%d %d", &x, &y);
        a[x].push_back(y);
        grad[y]++;
    }
}

void rezolva(){
int p, i, u = 0, x;

    for (i = 1; i <= n; i++)
        if (grad[i] == 0) q[++u] = i;

    for (p = 1; p <= n; p++){
        x = q[p];
        for (i = 0; i < a[x].size(); i++){
            grad[a[x][i]]--;
            if (grad[a[x][i]] == 0) q[++u] = a[x][i];
        }
    }
}