Cod sursa(job #1087133)

Utilizator lorundlorund lorund Data 18 ianuarie 2014 22:59:12
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>
#include <bitset>

std::vector<int> graph[100], sol;
std::bitset<100> vis;

void dfs(int start){
    vis[start] = 1;
    for (unsigned i=0; i<graph[start].size(); ++i){
        if (!vis[graph[start][i]]){
            dfs(graph[start][i]);
        }
    }
    sol.push_back(start);
}

int main()
{
    int N, M;

    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; ++i){
        int x, y;

        scanf("%d %d", &x, &y);
        graph[x].push_back(y);
    }
    for (int i=1; i<=N; ++i){
        if (!vis[i]){
            dfs(i);
        }
    }
    for (int i=sol.size()-1; i>=0; --i){
        printf("%d ", sol[i]);
    }
    return 0;
}