2-EDGE CONNECTED GRAPH

2-edge connected graph means the graph is always connected if we remove any edge of that graph.
For checking a graph is a two-edge connected graph , we just need to check whether for every sub-tree
of the graph there should be an edge going from that sub-tree to outside vertex and that vertex is
already visited.This can be solved by using DFS and in linear time.
PSUEDOCODE :
The below code returns the minimum value of the arrival time of the back-edge that the sub-tree is connected with.


time=0;
2edgeconnected(v) 
{
visited[v]=1;
arr[v]=time++;
int xyz=arr[v];  
for all w adjecent to v do
{
if(!visited[w])
 xyz=min(xyz,2edgeconnected(w));
else
 xyz=min(xyz,arr[w]);
}
if(xyz==arr[v])
  abort            //graph is not two-edge connected.
return xyz;
}
2 Likes

nice one!!

Equality will hold for the root node, u need to take care of that case

Equality will hold for the root node, u need to take care of that case

Useful oneā€¦

But same problem can be solved by following two checks:

  1. Graph is connected (Simple DFS)
  2. Graph does not contains a bridge. (Another DFS) Read more about bride finding here.

If both of above two conditions hold true, graph is 2-edge connected.

Time Complexity of this Solution: O(N+M)

Above two DFS can also be combined into a single DFS to improve time complexity.

Anyways, Nice editorial.