luisoncpp

Tarjan Implementation

Mar 17th, 2021
838
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using std::vector;
  5. using std::stack;
  6.  
  7. struct Tarjan {
  8.     Tarjan(vector<vector<int>> vecinos) : Vecinos(vecinos) {}
  9.     vector<vector<int>> SCC() && {
  10.       for (int i = 0; i < N; ++i) {
  11.         if (!Visitado[i]) {
  12.             dfs(i);
  13.         }
  14.       }
  15.       return Salida;
  16.     }
  17.   private:
  18.     const vector<vector<int>> Vecinos;
  19.     const int N = Vecinos.size();
  20.     vector<int> Visitado = vector<int>(N, 0);
  21.     vector<int> ArcoMasAlto = vector<int>(N, 0);
  22.     vector<bool> EnPila = vector<bool>(N, false);
  23.     stack<int> Pila;
  24.     vector<vector<int>> Salida;
  25.     int num_visitados = 0;
  26.  
  27.     void dfs(int v) {
  28.       ++num_visitados;
  29.       Visitado[v] = num_visitados;
  30.       ArcoMasAlto[v] = num_visitados;
  31.       Pila.push(v);
  32.       EnPila[v] = true;
  33.       for (int vecino : Vecinos[v]) {
  34.           if (!Visitado[vecino]) {
  35.               dfs(vecino);
  36.               ArcoMasAlto[v] = std::min(ArcoMasAlto[v], ArcoMasAlto[vecino]);
  37.           } else if (EnPila[vecino]) {
  38.               ArcoMasAlto[v] = std::min(ArcoMasAlto[v], Visitado[vecino]);
  39.           }
  40.       }
  41.       if (ArcoMasAlto[v] == Visitado[v]) {
  42.           vector<int> componente;
  43.           while (!Pila.empty() && Visitado[Pila.top()] >= Visitado[v]) {
  44.               componente.push_back(Pila.top());
  45.               EnPila[Pila.top()] = false;
  46.               Pila.pop();
  47.           }
  48.           Salida.push_back(std::move(componente));
  49.       }
  50.     }
  51. };
  52.  
  53. int main() {
  54.   std::vector<std::vector<int>> listas_de_adyacencia = {
  55.     {2},
  56.     {0, 4, 7},
  57.     {},
  58.     {1, 3, 7},
  59.     {3, 4},
  60.     {},
  61.     {3, 5},
  62.     {6}
  63.   };
  64.   auto salida = Tarjan(listas_de_adyacencia).SCC();
  65.   for (auto& vec : salida) {
  66.     for (int v : vec) {
  67.       std::cout << v << " ";
  68.     }
  69.     std::cout << std::endl;
  70.   }
  71.   return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment