Cod sursa(job #2610377)

Utilizator Miruna_OrzataOrzata Miruna-Narcisa Miruna_Orzata Data 4 mai 2020 19:55:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100009 // numar maxim de noduri

class Task {
public:
  void solve() {
    read_input();
    print_output(get_result());
  }

private:
  int n, m;
  vector<int> adj[NMAX];

  void read_input() {
    ifstream fin("sortaret.in");
    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {
      int x, y;
      fin >> x >> y;

      adj[x].push_back(y);
    }
    fin.close();
  }

  vector<int> get_result() {
    vector<int> topsort;

    vector<int> visited(n + 1, 0);

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

    reverse(topsort.begin(), topsort.end());

    return topsort;
  }

  void dfs(int node, vector<int> &visited, vector<int> &topsort) {
    visited[node] = 1;

    for (auto &it : adj[node]) {
      if (!visited[it]) {
        dfs(it, visited, topsort);
      }
    }

    topsort.push_back(node);
  }

  void print_output(vector<int> result) {
    ofstream fout("sortaret.out");
    for (int i = 0; i < (int)result.size(); ++i) {
      fout << result[i] << " ";
    }
    fout << "\n";
  }
};

int main() {
  Task *task = new Task();
  task->solve();
  delete task;

  return 0;
}