Cod sursa(job #3229735)

Utilizator dorin.ileailea dorin dorin.ilea Data 17 mai 2024 11:00:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.97 kb
#include <bits/stdc++.h>
using namespace std;

// define maxint
#define MAXINT 0x3f3f3f3f

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];

  // parent[node] = parent of node in the DFS traversal
  vector<int> parent;

  // found[node] = the timestamp when node was found (when started to visit its
  // subtree) Note: The global timestamp is incremented everytime a node is
  // found.
  vector<int> found;

  // the minimum accessible timestamp that node can see/access
  // low_link[node] =  min { found[x] | x is node OR x in ancestors(node) OR x
  // in descendants(node) };
  vector<int> low_link;

  // visiting stack: nodes are pushed into the stack in visiting order
  stack<int> nodes_stack;

  // in_stack[node] = true, if node is in stack
  //                  false, otherwise
  vector<bool> in_stack;

  void read_input() {
    ifstream fin("ctc.in");
    fin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
      fin >> x >> y;
      adj[x].push_back(y);  // arc (x, y)
    }
    fin.close();
  }

  vector<vector<int>> tarjan_scc() {
    // initialize results
    parent = vector<int>(n + 1, -1);
    found = vector<int>(n + 1, -1);
    low_link = vector<int>(n + 1, -1);
    in_stack = vector<bool>(n + 1, false);

    //  visit all nodes
    vector<vector<int>> all_sccs;
    int timestamp = 0;
    for (int node = 1; node <= n; node++) {
      if (parent[node] == -1) {
        parent[node] = node;
        dfs(node, timestamp, all_sccs);
      }
    }
    return all_sccs;
  }

  void dfs(int node, int& ref_timestamp, vector<vector<int>>& all_sccs) {
    found[node] = ++ref_timestamp;
    low_link[node] = found[node];
    nodes_stack.push(node);
    in_stack[node] = true;

    for (auto& neigh : adj[node]) {
      if (parent[neigh] != -1) {
        // check if neigh is in the stack
        if (in_stack[neigh]) {
          low_link[node] = min(low_link[node], found[neigh]);
        }
        continue;
      }
      parent[neigh] = node;

      dfs(neigh, ref_timestamp, all_sccs);

      low_link[node] = min(low_link[node], low_link[neigh]);
    }

    // check if the node is the root of the scc
    if (found[node] == low_link[node]) {
      vector<int> scc;
      do {
        auto x = nodes_stack.top();
        nodes_stack.pop();
        in_stack[x] = false;

        scc.push_back(x);
      } while (scc.back() != node);

      all_sccs.push_back(scc);
    }
  }

  vector<vector<int>> get_result() {
    //
    // TODO: Găsiți componentele tare conexe  (CTC / SCC) ale grafului orientat
    // cu n noduri, stocat în adj.
    //
    // Rezultatul se va returna sub forma unui vector, fiecare element fiind un
    // SCC (adică tot un vector).
    // * nodurile dintr-un SCC pot fi găsite în orice ordine
    // * SCC-urile din graf pot fi găsite în orice ordine
    //
    // Indicație: Folosiți algoritmul lui Tarjan pentru SCC.
    //

    return tarjan_scc();
  }

  void print_output(const vector<vector<int>>& all_sccs) {
    ofstream fout("ctc.out");
    fout << all_sccs.size() << '\n';
    for (const auto& scc : all_sccs) {
      for (auto node : scc) {
        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;
}