/**
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 */classSolution{publicList<List<Integer>>criticalConnections(intn,List<List<Integer>>connections){int[]timeOfInsertion=newint[n];//dfs insertion time int[]lowestTimeOfInsertion=newint[n];// min of lowest insertion time of all adjacent node except parent//creating adjacency listList<List<Integer>>adj=newArrayList<>();for(inti=0;i<n;i++)adj.add(newArrayList<>());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));}intvisited[]=newint[n];List<List<Integer>>bridges=newArrayList<>();for(inti=0;i<n;i++){if(visited[i]==0){dfs(0,-1,adj,visited,bridges,0,timeOfInsertion,lowestTimeOfInsertion);}}returnbridges;}publicvoiddfs(intnode,intparent,List<List<Integer>>adj,intvisited[],List<List<Integer>>bridges,inttime,intt[],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(intadjNode: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, 9low[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---9if(t[node]<low[adjNode]){List<Integer>edge=newArrayList<>();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}}}}