Cod sursa(job #780805)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 august 2012 21:28:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int kMaxN = 50005;

vector<int> G[kMaxN];
int N, TSort[kMaxN];
bool V[kMaxN];

void DFS(const int X) {
    V[X] = true;
    for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y)
        if (!V[*Y])
            DFS(*Y);
    TSort[++TSort[0]] = X;
}

void Solve() {
    for (int X = 1; X <= N; ++X)
        if (!V[X])
            DFS(X);
    reverse(TSort+1, TSort+N+1);
}

void Read() {
    freopen("sortaret.in", "r", stdin);
    int M; scanf("%d %d", &N, &M);
    for (; M; --M) {
        int X, Y; scanf("%d %d", &X, &Y);
        G[X].push_back(Y);
    }
}

void Print() {
    freopen("sortaret.out", "w", stdout);
    for (int i = 1; i <= N; ++i)
        printf("%d ", TSort[i]);
    printf("\n");
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}