/*
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)
*/classMain{publicstaticvoidmain(Stringargs[]){intn=5;ArrayList<ArrayList<Integer>>adj=newArrayList<ArrayList<Integer>>();for(inti=0;i<n;i++)adj.add(newArrayList<Integer>());adj.get(0).add(1);adj.get(1).add(0);adj.get(0).add(2);adj.get(2).add(0);adj.get(1).add(2);adj.get(2).add(1);adj.get(1).add(3);adj.get(3).add(1);adj.get(3).add(4);adj.get(4).add(3);Mainobj=newMain();obj.printBridges(adj,n);}publicvoidprintBrides(ArrayList<ArrayList<Integer>>adjList,intn){intvisited[]=newint[n];inttimeOfInsertion[]=newint[n];intlowestTimeOfInstion[]=newint[n];inttimer=0;for(inti=0;i<n;i++){if(visited[i]==0){dfs(i,-1,visited,timeOfInsertion,lowestTimeOfInstion,adjList,timer);}}}publicvoiddfs(intnode,intparent,intvisted[],inttimeOfInsertion[],intlowestTimeOfInstion[],inttimer){visited[node]=1;timeOfInsertion[node]=lowestTimeOfInstion[node]=timer++;for(IntegeradjNode:adjList.get(node)){if(adjNode==parent)continue;// if adjacent node is parent node just continueif(visited[adjNode]==0){dfs(adjNode,node,visited,timeOfInsertion,lowestTimeOfInstion,adjList,timer);lowestTimeOfInstion[node]=Integer.min(lowestTimeOfInstion[node],lowestTimeOfInstion[adjNode]);// the case that check if the current edge is could be bridge or notif(lowestTimeOfInstion[adjNode]>timeOfInsertion[node]){System.out.println(adjNode+" "+node);}}elselowestTimeOfInstion[node]=Integer.min(lowestTimeOfInstion[node],timeOfInsertion[adjNode]);}}