Cod sursa(job #940578)

Utilizator andreiagAndrei Galusca andreiag Data 16 aprilie 2013 17:51:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

typedef vector<int>::iterator iter_v;
const int SIZE = 50001;
int N, M;
map<int, vector<int> > G;
bool visited[SIZE];
vector<int> order;

void dfs(int start)
{
    if (!visited[start]) {
        visited[start] = true;
        vector<int> &v = G[start];
        for(iter_v it = v.begin(); it != v.end(); ++it) {
            if (!visited[*it]) dfs(*it);
        }
        order.push_back(start);
        //cout << start << endl;
    }
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int a, b;
    scanf("%d %d", &N, &M);
    for(int i = 0; i < M; i++) {
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
    }
    for(int i = 1; i <= N; i++)
        dfs(i);
    printf("%d", order[N-1]);
    for(int i = N - 2; i >= 0; i--)
        printf(" %d", order[i]);
    printf("\n");

    return 0;
}