Cod sursa(job #1890211)

Utilizator stanciuandreiStanciulescu Andrei stanciuandrei Data 23 februarie 2017 10:10:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
/*
    Sortare topologica: metoda cu arbore (DFS)
*/

#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 50000 + 4

using namespace std;

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

bool visited[NMAX];
vector<int> graph[NMAX];
vector<int> solution;

int n, m, x, y;

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

int main()
{
    in>>n>>m;
    for(int i=0;i<m;i++){
        in>>x>>y;
        graph[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        if(!visited[i])
            dfs(i);
    }
    for(int i=solution.size()-1;i>=0;i--)
        out<<solution[i]<<' ';
    out<<'\n';
    return 0;
}