Cod sursa(job #1118640)

Utilizator swim406Teudan Adina swim406 Data 24 februarie 2014 12:23:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define nmax 50001

using namespace std;

queue <int> q;
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])
            q.push(i);
    while (!q.empty()) {
        x = q.front();
        q.pop();
        printf ("%d ", x);
        m = G[x].size();
        for (i = 0; i < m; ++i) {
            y = G[x][i];
            --deg[y];
            if (!deg[y]) q.push(y);
        }
    }
    return 0;
}