getBcc

std::vector<std::vector<std::pair<int, int>>> getBccV(const std::vector<std::vector<int>>& g) {
  int n = int(g.size());

  std::vector<int> dep(n, -1);
  std::vector<int> low(n);
  std::vector<std::pair<int, int>> stk;
  std::vector<std::vector<std::pair<int, int>>> bcc;

  auto dfs = [&](auto&& dfs, int u, int p) -> void {
    for (int v : g[u]) {
      assert(0 <= v && v < n);
      if (v == p) {
        continue;
      }
      if (dep[u] > dep[v]) {
        stk.emplace_back(u, v);
      }
      if (dep[v] != -1) {
        low[u] = std::min(low[u], dep[v]);
      } else {
        low[v] = dep[v] = dep[u] + 1;
        dfs(dfs, v, u);
        low[u] = std::min(low[u], low[v]);
        if (dep[u] <= low[v]) {
          std::vector<std::pair<int, int>> new_bcc;
          while (true) {
            auto [x, y] = stk.back();
            stk.pop_back();
            new_bcc.emplace_back(x, y);
            if (x == u && y == v) {
              break;
            }
          }
          bcc.push_back(std::move(new_bcc));
        }
      }
    }
  };

  for (int i = 0; i < n; ++i) {
    if (dep[i] == -1) {
      low[i] = dep[i] = 0;
      dfs(dfs, i, -1);
    }
  }

  return bcc;
}

std::vector<std::vector<int>> getBccE(const std::vector<std::vector<int>>& g) {
  int n = int(g.size());

  std::vector<int> dep(n, -1);
  std::vector<int> low(n);
  std::vector<int> stk;
  std::vector<std::vector<int>> bcc;

  auto dfs = [&](auto&& dfs, int u, int p) -> void {
    for (int v : g[u]) {
      assert(0 <= v && v < n);
      if (v == p) {
        continue;
      }
      if (dep[v] != -1) {
        low[u] = std::min(low[u], dep[v]);
      } else {
        low[v] = dep[v] = dep[u] + 1;
        dfs(dfs, v, u);
        low[u] = std::min(low[u], low[v]);
      }
    }

    if (low[u] == dep[u]) {
      std::vector<int> new_bcc;
      while (true) {
        int x = stk.back();
        stk.pop_back();
        new_bcc.push_back(x);
        if (x == u) {
          break;
        }
      }
      bcc.push_back(std::move(new_bcc));
    }
  };

  for (int i = 0; i < n; ++i) {
    if (dep[i] == -1) {
      low[i] = dep[i] = 0;
      dfs(dfs, i, -1);
    }
  }

  return bcc;
}