Cod sursa(job #866350)

Utilizator sana1987Laurentiu Dascalu sana1987 Data 27 ianuarie 2013 21:25:11
Problema Sortare topologica Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>

using namespace std;

#define S 50000

static vector<int> graph[S];
static int Q[S];
static int indegree[S];

int main(int argc, char **argv) {
    int N, M;
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d %d\n", &N, &M);

    for (int i = 0; i < N; i++) indegree[i] = 0;

    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d\n", &u, &v);
        u--; v--;
        graph[u].push_back(v);
        indegree[v]++;
    }

    for (int i = 0; i < N; i++) {
        if (indegree[i] == 0) {
            Q[++Q[0]] = i;
        }
    }

    for (int i = 0; i < N; i++) {
        for (vector<int>::iterator it = graph[Q[i]].begin(); it != graph[Q[i]].end(); it++) {
            indegree[*it]--;
            if (indegree[*it] == 0) {
                Q[++Q[0]] = *it;
            }
        }
    }

    for (int i = 1; i <= Q[0]; i++) {
        printf("%d ", Q[i] + 1);
    }

    return 0;
}