Cod sursa(job #3229734)

Utilizator dorin.ileailea dorin dorin.ilea Data 17 mai 2024 10:56:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 kb
#include <bits/stdc++.h>
using namespace std;

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

 private:
  // numarul maxim de noduri
  static constexpr int NMAX = (int)1e5 + 5;  // 10^5 + 5 = 100.005

  // n = numar de noduri, m = numar de muchii/arce
  int n, m;

  // adj[node] = lista de adiacenta a nodului node
  // exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
  vector<int> adj[NMAX];

  void read_input() {
    ifstream fin("sortaret.in");
    fin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
      fin >> x >> y;  // arc (x, y)
      adj[x].push_back(y);
    }
    fin.close();
  }
  void dfs(vector<int>& visited, vector<int>& parents, vector<int>& start,
           vector<int>& finish, vector<int>& topsort) {
    int timestamp = 0;
    for (int i = 1; i <= n; i++) {
      if (visited[i] == 0) {
        dfs_rec(i, visited, parents, start, finish, timestamp, topsort);
      }
    }
  }

  void dfs_rec(int node, vector<int>& visited, vector<int>& parents,
               vector<int>& start, vector<int>& finish, int& ref_timestamp,
               vector<int>& topsort) {
    start[node] = ++ref_timestamp;
    visited[node] = 1;

    for (auto& neigh : adj[node]) {
      if (visited[neigh] == 0) {
        parents[neigh] = node;
        dfs_rec(neigh, visited, parents, start, finish, ref_timestamp, topsort);
      }
    }

    finish[node] = ++ref_timestamp;
    // use node
    topsort.push_back(node);
    visited[node] = 2;
  }

  vector<int> get_result() {
    // TODO: Faceti sortarea topologica a grafului stocat cu liste de adiacenta
    // din adj.
    // *******
    // ATENTIE: nodurile sunt indexate de la 1 la n.
    // *******

    vector<int> topsort;
    // add by me
    vector<int> parents(n + 1, 0);
    vector<int> visited(n + 1, 0);
    vector<int> start(n + 1, 0);
    vector<int> finish(n + 1, 0);
    dfs(visited, parents, start, finish, topsort);
    // reverse topsort
    reverse(topsort.begin(), topsort.end());
    return topsort;
  }

  void print_output(const vector<int>& topsort) {
    ofstream fout("sortaret.out");
    for (auto node : topsort) {
      fout << node << ' ';
    }
    fout << '\n';
    fout.close();
  }
};

// [ATENTIE] NU modifica functia main!
int main() {
  // * se aloca un obiect Task pe heap
  // (se presupune ca e prea mare pentru a fi alocat pe stiva)
  // * se apeleaza metoda solve()
  // (citire, rezolvare, printare)
  // * se distruge obiectul si se elibereaza memoria
  auto* task = new (nothrow) Task();  // hint: cppreference/nothrow
  if (!task) {
    cerr << "new failed: WTF are you doing? Throw your PC!\n";
    return -1;
  }
  task->solve();
  delete task;
  return 0;
}