Algorithm for finding articulation points and bridges in network.

//TODO improve

Algorithm to find a bridges

1. Build graph
2. Create low and disc arrays. 
		low - lowest node accessible from current and 
		disc - time when node was discovered
3. Init time = 0
4. Go dfs from each node if it's not discovered (visited)
5. Keep track of current and previous
6. Iterate through neighbors and if curr != prev continue
7. Now we have two cases, node either discovered or not.
	a) If discovered then low[src] = Math.min(low[src], disc[nei])
	b) If NOT then low[src] = Math.min(low[src], low[nei])
		 and if low[dst] > disc[src] then add to bridge

Implementation Critical Connections LC hard

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
      List<Integer>[] graph = new List[n];
      for (int i = 0; i < n; i++) {
          graph[i] = new ArrayList<>();
      }
      for (List<Integer> conn : connections) {
          int src = conn.get(0);
          int dest = conn.get(1);
          graph[src].add(dest);
          graph[dest].add(src);
      }

      int[] low = new int[n];
      int[] disc = new int[n];
      Arrays.fill(disc, -1);
      List<List<Integer>> bridges = new ArrayList<>();

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

  int time = 0; // time when discover each vertex

  private void dfs(List<Integer>[] graph, int src, int prev,
                   List<List<Integer>> bridges, int[] disc, int[] low) {
      low[src] = disc[src] = ++time;
      for (int dst : graph[src]) {
          if (prev == dst) continue;
          if (disc[dst] == -1) {
              dfs(graph, dst, src, bridges, disc, low);
              low[src] = Math.min(low[src], low[dst]);
              if (low[dst] > disc[src]) {
                  //critical path found
                  bridges.add(List.of(src, dst));
              }
          } else {
              // if dst discovered and is not parent of src, update low[src], cannot use low[dst] because u is not subtree of dst
              low[src] = Math.min(low[src], disc[dst]);
          }
      }
  }

Time complexity

O(V + E)

Space

O(V)

Resources

Bridges and Articulation points Algorithm | Graph Theory

Tarjans Strongly Connected Components algorithm | Graph Theory

Critical Connections in a Network - LeetCode