Cod sursa(job #469208)

Utilizator vlad.maneaVlad Manea vlad.manea Data 6 iulie 2010 22:24:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <cstdio>
#include <cstdlib>
#include <queue>

#define nmax 50005

using namespace std;

int N, M, x, y;
int G[nmax], *T[nmax], order[nmax];

// reads

void read() {

    // set input file
    freopen("sortaret.in", "r", stdin);

    // read vertexes and lines
    scanf("%d%d", &N, &M);

    // set initial values
    for (int i = 1; i <= N; ++i) {
        T[i] = (int*) realloc(T[i], sizeof (int));
        T[i][0] = 0;
    }

    // set vertex degrees
    for (int i = 0; i < M; ++i) {
        scanf("%d%d", &x, &y);
        T[y][0]++;
        G[x]++;
    }

    // set vertex lists
    for (int i = 1; i <= N; ++i) {
        T[i] = (int*) realloc(T[i], (1 + T[i][0]) * sizeof (int));
        T[i][0] = 0;
    }

    // go back to read
    fseek(stdin, 0, SEEK_SET);

    // read vertexes and lines
    scanf("%d%d", &x, &y);

    // read lines
    for (int i = 0; i < M; ++i) {
        scanf("%d%d", &x, &y);
        T[y][++T[y][0]] = x;
    }
}

// solve

void solve() {

    // create queue
    queue<int> Q;

    // put all elements of zero degree in queue
    for (int i = 1; i <= N; ++i) {
        if (G[i] == 0) {
            Q.push(i);
        }
    }

    // iterate queue
    while (!Q.empty()) {

        // get element
        int e = Q.front();

        // put first element
        order[++order[0]] = e;

        // iterate neighbors, by decreasing their degree
        for (int i = 1; i <= T[e][0]; ++i) {
            G[T[e][i]]--;

            // have to add to queue?
            if (G[T[e][i]] == 0) {
                Q.push(T[e][i]);
            }
        }

        // delete first element
        Q.pop();

    }

}

// write

void write() {

    // set output file
    freopen("sortaret.out", "w", stdout);

    // set initial values
    for (int i = N; i >= 1; --i) {
        printf("%d ", order[i]);
    }

    printf("\n");

}

int main() {

    // reads
    read();

    // solves
    solve();

    // writes
    write();

    // done
    return 0;
}