Bridges in the graph

Problem

/**
Bridges in the graph.
Those edges in the graph whose removal will result 
in 2 or more components in the graph are called as bridges in the graph.
Consider the below example:
1-------2
|       |
|       |
4-------3
|
|
5-------6
        /\
       /  \
      7    9
      \    /
       \  /
         8
         |
         |
         10---11
          |   /
          |  /
           12

edge between 4 and 5 is called bridge, 
edge between 5 and 6 is bridge
edge between 8 and 10 is bride.

We will be using two things in the algorithm (We will be using depth first search algorithm)
Time of Insertion of the node
Lowest time of Insertion of the node 
Time complexity is : O(n +e)
Space complexity is : O(2n)~ O(n)

We will use Tarjan's algorithm for finding the bridges in the graph
we will keep two array
timeOfInsertion[], lowestTimeOfInsertion[]
note: timeOfInsertion will keep track of step/time at which a node was visited(we will use dfs for traversing the nodes)
lowestTimeOfInsertion[]: will be updated as and when we  visit adjacent nodes, initially the unvisited nodes will have same timeOfInsertion and lowestTimeOfInsertion. But when we will encounter a neighour node say B of current node A(parent) that is already visited(B) ( which is not parent of A). we will updated the lowestTimeOfInsertion[] for the node A such that lowestTimeOfInsertion[A] = min(lowestTimeOfInsertion[A], lowestTimeOfInsertion[B])


at the end of a dfs call  if node----adjacetNode can be removed ( to check if they form component)
if the timeOfInserstion[node] > lowestTimeOfInsertion[adjacentNode] then node can still reach from someother adjacentNode  node----AdjancentNode is not a bridge

Similary we will do for rest of the nodes and determine the bridge in the given graph */

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        int[] timeOfInsertion =  new int[n];//dfs insertion time 
        int[] lowestTimeOfInsertion = new int[n];// min of lowest insertion time of all adjacent node except parent

        //creating adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for(int i =0;i<n;i++) adj.add(new ArrayList<>());
        for(List<Integer> list : connections){
            //since the edge are undirected hence 
            adj.get(list.get(0)).add(list.get(1));
            adj.get(list.get(1)).add(list.get(0));
        }

        int visited[] = new int[n];
        List<List<Integer>> bridges = new ArrayList<>();
        for(int i =0;i<n;i++){
            if(visited[i]== 0){
                dfs(0,-1,adj,visited,bridges,0,timeOfInsertion,lowestTimeOfInsertion);
            }
        }
        return bridges;
    }
    public void dfs(int node, int parent, List<List<Integer>> adj, int visited[] , List<List<Integer>> bridges,int time, int t[] , int[] low){
        visited[node] = 1;
        t[node] =low[node] = time++;

/*
5-------6
        /\
       /  \
      7    9 Say, we are at 9 in dfs coming from 8(parent) 6,7 are visited already
      \    / note: lowestTimeOfInsertion[6] = 6 and lowestTimeOfInsertion[9] = 9 => it will be updated 
       \  /  as min of both hence lowestTimeOfInsertion[9] =6, meaning from 9 it is possible to reach 
         8   at node with lowest insertion time of 6 hence any higher insertion time(>6) node can also 
             be reached from 9 (i.e if 8----9 is removed then also we can reach 8 since now the lowestTimeOfInsertion[9] is 6, so from 9 to 6 to 7 to 8 is possible, hence 8---9 is not bridge)
         */
        for(int adjNode : adj.get(node)){
            if(adjNode == parent) continue;
            if(visited[adjNode] ==0){
                dfs(adjNode,node,adj,visited,bridges,time,t,low); 
                //from the example above once the dfs traversal of 9 is done it will come back to 8, hence 8 will updated its lowestTimeOfInsertion as well by choosing min of low of 8, 9
                low[node] = Integer.min(low[node],low[adjNode]);
                //after 8(node) updates its lowestTimeOfInsertion it check if (node)8---9(adjNode) could be a bridge or not

                // if the timeOfinssertion[node] < lowestTimeOfInsertion[adjNode] then it is not possible for adjNode(9) to reach to node(8) hence this will form bridge else not a bride 8---9
                if(t[node] < low[adjNode]) {
                    List<Integer> edge = new ArrayList<>();
                    edge.add(node);
                    edge.add(adjNode);
                    bridges.add(edge);
                }
            }
            else{
                low[node] = Integer.min(low[node],low[adjNode]); // if the adjNode is visited ( in above example 6) update the lowestTimeOfInsertion[9] = min of lowestTimeOfInsertion of 6 and 9
            }
        }
    }
}

For more detailed explanation refer

Articulation point in graph