Algorithm (Offline Bridge Finding)

This problem is a model problem for the classic Tarjan bridge finding algorithm. Given a graph $G$ and its $\texttt{root}$. We have the following observation:

• Suppose we are in the process of DFS, and now we are at $v$ and looking at one of its neighbors, $to$. Then the edge $(v,to)$ is a bridge if and only if none of the vertices to $to$ and its descendants in the DFS traversal tree has back-edge to vertex $v$ or any of its ancestors. This means that there is not other way from $v$ to $to$ except for the edge $(v,to)$.

So the key to developing an efficient algorithm replies on looking at the entry time for each of the node and using the previous observation.

1. Let $\tau(v)$ be the entry time for vertex $v$ of $G$ and $\ell(v)$ be the minimum of $\tau(v)$, the entry times $\tau(p)$ for each node $o$ that is connected to $v$ via a back-edge $(v,p)$ and value of $\ell(to)$ for all $to$ such that $to$ is a direct descendant of $v$ in the DFS tree.
2. Mathematically, we have that $$\ell(v)=\min\begin{cases} \tau(v)\\\\ \tau(p) & \text{for all }p\text{ s.t. }(v,p)\text{ is a back edge}\\\\ \ell(to) & \text{for all }to\text{ s.t. }(v,to)\text{ is a tree edge} \end{cases}.$$
3. Now, we note that there exists a back edge from vertex $v$ to one of its descendants to one of its ancestors if and only if $v$ has a child $to$ such that $\ell(to)\leq\tau(v).$ If $\ell(to)=\tau(v),$ the back edge comes directly to $v$, otherwise $to$ visits one of $v$’s ancestors.
4. Therefore, the current edge $(v,to)$ in the DFS tree is a bridge if and only if $\ell(to)>\tau(v).$
5. This process could be implemented using tree DP ideas.
6. The resulting complexity is $O(\left|V\right|+\left|E\right|)$ since we only run dfs once.
7. We use Cpp17 features. When Cpp20 comes out, SFNAE dispatch pattern will be switched to concepts.
8. Interested readers should try to implement similar collect for adjacency_matrix type class.
9. If you are really hard core, you can try to think of a way to make collect lazy in the sense that it can grow by being called multiple times. For example, collect(graph).materialize() finish the computation. collect(graph).take(n) takes the next $n$ bridges if they exists. collect(graph).take(1).take(2).materialize() finish the whole computing cycle by returning 3 bridges if found or a false flag std::nullopt if no bridge exists. I can think of one way to implement it but it requiires some unpleasant cpp hacking, which is bad for a couple of reasons. If you have a good idea on how to code this up elegantly please PM me. My line of thought on this:
   1. Change collect‘s signature from a function to a struct and overload its () operator.
   2. Inside the collect struct, we also define take which does the computation.

Code

namespace graph::representation {
class adjacency_list {};
class adjacency_matrix {};
class edge_list {};
};


namespace graph::connectivity {
class abstract_properties {};
class bridge : virtual public abstract_properties {};
class articulation_point : virtual public abstract_properties {};
class connected_component : virtual public abstract_properties {};
} 

template <typename property_t,
          typename vertex_t = int,
          typename result_t = std::array<vertex_t, 2>,
          typename graph_t = graph::representation::adjacency_list,
          typename std::enable_if_t<std::is_same_v<graph::connectivity::bridge, property_t>>* = nullptr,
          typename std::enable_if_t<std::is_same_v<graph::representation::adjacency_list, graph_t>>* = nullptr>
vector<result_t> collect(const vector<vector<vertex_t>>& graph) {
  vector<result_t> result = {};
  auto entry_time = vector<int>(size(graph), 0);
  auto low        = vector<int>(size(graph), 0);
  auto vis        = vector<int>(size(graph), false);

  auto dfs = rec([&, timer = 0](auto&& dfs, int v, optional<vertex_t> parent = {}) mutable -> void {
    vis[v] = true;
    entry_time[v] = low[v] = timer++;
    for (const vertex_t to : graph[v]) {
      if (parent and to == *parent)
        continue;
      else if (vis[to]) 
        low[v] = std::min(low[v], entry_time[to]);
      else {
        dfs(to, v);
        low[v] = std::min(low[v], low[to]);
        if (low[to] > entry_time[v])
          result.emplace_back(result_t{v, to});
      }
    }
  });

  for (int i = 0; i < size(graph); ++i) 
    if (not vis[i])
      dfs(i);

  return result;
}


class Solution {
 public:
  vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    using namespace graph::connectivity;

    const auto adjlist = [&](vector<vector<int>> self = {}) {
      self.assign(n, vector<int>());
      for (const auto & e : connections) {
        self[e[0]].emplace_back(e[1]);
        self[e[1]].emplace_back(e[0]);
      };
      return self;
    }();

    return collect<bridge, int, vector<int>>(adjlist);
  }
};

Reference

1. https://cp-algorithms.com/graph/bridge-searching.html