Cod sursa(job #1712619)

Utilizator dcutitoiuCutitoiu Adrian-Nicolae dcutitoiu Data 3 iunie 2016 09:50:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <iterator>
#include <algorithm>
#include <tuple>

using namespace std;

void DFS(int current, const vector<vector<int>> &adj, vector<bool> &vizitat, vector<int> &order){
    vizitat[current] = true;

    for(auto nod : adj[current]){
        if(!vizitat[nod])
            DFS(nod, adj, vizitat, order);
    }

    order.push_back(current);
}

int main(){

    int N,M,x,y;

    ifstream in ("sortaret.in");
    ofstream out ("sortaret.out");

    in >> N >> M;
    vector<vector<int>>adj(N+1);

    for(int i = 1; i <= M; i++){
        in >> x >> y;

        adj[x].push_back(y);
    }

    vector<int> order;
    vector<bool> vizitat(N+1);

    for(int i = 1; i <= N; i++){
        if(!vizitat[i])
            DFS(i, adj, vizitat, order);
    }

    copy(order.rbegin(), order.rend(), ostream_iterator<int>(out, " "));

    return 0;
}