Cod sursa(job #2610524)

Utilizator RobertLicaRobert Lica RobertLica Data 4 mai 2020 23:11:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

#define FILE_I "sortaret.in"
#define FILE_O "sortaret.out"

class Task {
  int n, m;
  std::vector< std::vector< int>> adj;
  std::vector<int> t_out;
  int pas = 1;

 public:
  void solve() {
    read();
    fa();
    print();
  }

 private:
  void read() {
    std::ifstream fin(FILE_I);
    fin >> n >> m;
    adj.resize(n + 1);

    int x, y;
    for (int i = 0; i < m; ++i) {
      fin >> x >> y;
      adj[x].push_back(y);
    }
    fin.close();
  }

  void fa() {
    std::vector<int> vizitat(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
      if (vizitat[i] == 0) {
        dfs(i, vizitat);
        t_out.push_back(i);
      }
    }
  }

  void dfs(int nod, std::vector<int> &vizitat) {
    vizitat[nod] = 1;
    for (auto &x : adj[nod]) {
      if (vizitat[x] == 0) {
        dfs(x, vizitat);
        t_out.push_back(x);
      }
    }
  }

  void print() {
    std::ofstream fout (FILE_O);
    for (auto x = (t_out.end() - 1); x >= t_out.begin(); --x) {
      fout << *x << " ";
    }
    fout.close();
  }
};

int main() {
  Task *t = new Task();
  t->solve();
  delete t;
  return 0;
}