Cod sursa(job #2486539)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 3 noiembrie 2019 08:13:20
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define N_MAX 50001
using namespace std;

int N, M;
vector<vector<int>> graph(N_MAX, vector<int>());

vector<int> visited(N_MAX, false);

stack<int> top_sort;

void dfs(int node)
{
    visited[node] = true;

    for(auto& next : graph[node])
    {
        if(visited[next] == false) dfs(next);
    }

    top_sort.push(node);
}

int main()
{
    ifstream fin{"sortaret.in"};
    ofstream fout{"sortaret.out"};

    fin >> N >> M;

    for(int x, y, i = 1; i <= M; ++i)
    {
        fin >> x >> y;
        graph[x].push_back(y);
    }

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

    while(top_sort.empty() == false)
    {
        fout << top_sort.top() << " ";
        top_sort.pop();
    }
}