Cod sursa(job #903641)

Utilizator swim406Teudan Adina swim406 Data 1 martie 2013 23:55:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <vector>

using namespace std;

int Q[50001];
vector <int> G[50001];

int main() {
    freopen ("sortaret.in", "r", stdin);
    freopen ("sortaret.out", "w", stdout);
    int N, M, x, y, deg[50001], count = 0, i, m;
    scanf ("%d %d", &N, &M);
    for (i = 1; i <= N; ++i)
        deg[i] = 0;
    for (i = 1; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].push_back(y);
        ++deg[y];
    }
    for (i = 1; i <= N; ++i)
        if (deg[i] == 0)
            Q[++Q[0]] = i;
    for (i = 1; i <= N; ++i) {
        x = Q[i];
        for (int j = 0; j < G[x].size(); ++j) {
            m = G[x][j];
            --deg[G[x][j]];
            if (deg[G[x][j]] == 0)
                Q[++Q[0]] = G[x][j];
        }
    }
    for (i = 1; i <= N; ++i) {
        printf ("%d ", Q[i]);
    }
    return 0;
}