# 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.