Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- using std::vector;
- using std::stack;
- struct Tarjan {
- Tarjan(vector<vector<int>> vecinos) : Vecinos(vecinos) {}
- vector<vector<int>> SCC() && {
- for (int i = 0; i < N; ++i) {
- if (!Visitado[i]) {
- dfs(i);
- }
- }
- return Salida;
- }
- private:
- const vector<vector<int>> Vecinos;
- const int N = Vecinos.size();
- vector<int> Visitado = vector<int>(N, 0);
- vector<int> ArcoMasAlto = vector<int>(N, 0);
- vector<bool> EnPila = vector<bool>(N, false);
- stack<int> Pila;
- vector<vector<int>> Salida;
- int num_visitados = 0;
- void dfs(int v) {
- ++num_visitados;
- Visitado[v] = num_visitados;
- ArcoMasAlto[v] = num_visitados;
- Pila.push(v);
- EnPila[v] = true;
- for (int vecino : Vecinos[v]) {
- if (!Visitado[vecino]) {
- dfs(vecino);
- ArcoMasAlto[v] = std::min(ArcoMasAlto[v], ArcoMasAlto[vecino]);
- } else if (EnPila[vecino]) {
- ArcoMasAlto[v] = std::min(ArcoMasAlto[v], Visitado[vecino]);
- }
- }
- if (ArcoMasAlto[v] == Visitado[v]) {
- vector<int> componente;
- while (!Pila.empty() && Visitado[Pila.top()] >= Visitado[v]) {
- componente.push_back(Pila.top());
- EnPila[Pila.top()] = false;
- Pila.pop();
- }
- Salida.push_back(std::move(componente));
- }
- }
- };
- int main() {
- std::vector<std::vector<int>> listas_de_adyacencia = {
- {2},
- {0, 4, 7},
- {},
- {1, 3, 7},
- {3, 4},
- {},
- {3, 5},
- {6}
- };
- auto salida = Tarjan(listas_de_adyacencia).SCC();
- for (auto& vec : salida) {
- for (int v : vec) {
- std::cout << v << " ";
- }
- std::cout << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment