Cod sursa(job #1414563)

Utilizator gallexdAlex Gabor gallexd Data 2 aprilie 2015 19:16:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>
using namespace std;

int N, M, x, y;
vector<int> graph[50010], sorted;
int viz[50010];

void dfs(int node) {
    for (vector<int>::iterator it=graph[node].begin(); it!=graph[node].end(); ++it) {
        if (!viz[*it]) {
            viz[*it] = true;
            dfs(*it);
        }
    }
    sorted.push_back(node);
}

int main () {

    freopen("sortaret.in", "rt", stdin);
    freopen("sortaret.out", "wt", stdout);

    scanf("%d %d", &N, &M);
    for (;M;--M) {
        scanf("%d %d", &x, &y);
        graph[x].push_back(y);
    }

    for (int i=1; i<=N; ++i) {
        if (!viz[i]) {
            viz[i] = true;
            dfs(i);
        }
    }

    for(int i = sorted.size()-1; i>=0; --i)
        printf("%d ", sorted[i]);

    return 0;
}