Cod sursa(job #1173628)

Utilizator lorundlorund lorund Data 20 aprilie 2014 12:08:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

int N, M;
vector<int> graph[50005];
vector<int> sol;
bitset<50005> visited;

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

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

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; ++i){
        int from, to;
        scanf("%d %d", &from, &to);
        graph[from].push_back(to);
    }

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

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