Cod sursa(job #3195390)

Utilizator BogdanPPBogdan Protopopescu BogdanPP Data 20 ianuarie 2024 18:01:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

#define nmax 50001

int n, m;
vector<vector<int>> graph(nmax);
vector<bool> visited(nmax);
stack<int> s;

void dfs(int node)
{
   visited[node] = true;
   for (auto neighbour : graph[node])
   {
      if (!visited[neighbour])
      {
         dfs(neighbour);
      }
   }
   s.push(node);
}

void read()
{
   fin >> n >> m;
   graph.resize(n + 1);
   visited.resize(n + 1);
   for (int i = 0; i < m; i++)
   {
      int x, y;
      fin >> x >> y;
      graph[x].push_back(y);
   }
}

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

   while (!s.empty())
   {
      fout << s.top() << " ";
      s.pop();
   }

   return 0;
}