Cod sursa(job #2203930)

Utilizator robertkarolRobert Szarvas robertkarol Data 13 mai 2018 18:39:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define NMAX 50001
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<vector<int> > graph;
int i,x,y,nrEdges,nrVertexes;
vector<bool> visited;
vector<int> topological_sort;
void dfs(int node)
{
    visited[node]=true;
    for(const auto& next : graph[node])
        if(!visited[next])
            dfs(next);
    topological_sort.push_back(node);
}
int main()
{
    fin>>nrVertexes>>nrEdges;
    graph.resize(nrVertexes+1);
    visited.resize(nrVertexes+1);
    for(i=1;i<=nrEdges;i++)
    {
        fin>>x>>y;
        graph[x].push_back(y);
    }
    for(i=1;i<=nrVertexes;i++)
        if(!visited[i])
            dfs(i);
    reverse(topological_sort.begin(), topological_sort.end());
    for(const auto& it : topological_sort)
        fout<<it<<" ";
    return 0;
}