Cod sursa(job #3264053)

Utilizator TudorNMnegoita tudor mihai TudorNM Data 17 decembrie 2024 20:52:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

const int nMAX = 100e3;
const int mMAX = 400e3;

int n, m;
vector<int> gf[nMAX + 1];
vector<int> gfsort;
bool viz[nMAX + 1];

void sortTop(int nod)
{
   for (int vec : gf[nod])
      if (!viz[vec])
      {
         viz[vec] = 1;
         sortTop(vec);
      }

   gfsort.push_back(nod);
}

int main()
{
   fin >> n >> m;
   for (int i = 1; i <= m; ++i)
   {
      int a, b;
      fin >> a >> b;
      gf[a].push_back(b);
   }

   for (int i = 1; i <= n; ++i)
      if (!viz[i])
      {
         viz[i] = 1;
         sortTop(i);
      }

   for (int i = gfsort.size() - 1; i >= 0; --i)
      fout << gfsort[i] << ' ';
}