You are not logged in. Please login at www.codechef.com to post your questions!

×

2-EDGE CONNECTED GRAPH

 2 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; } asked 03 Jul '14, 12:06 2★trek 327●4●12●18 accept rate: 0%

 0 nice one!! answered 03 Jul '14, 16:04 4★suryanit 11●1●3●4 accept rate: 0%
 0 Equality will hold for the root node, u need to take care of that case answered 06 Dec '17, 23:21 1 accept rate: 0%
 0 Equality will hold for the root node, u need to take care of that case answered 06 Dec '17, 23:22 1 accept rate: 0%
 0 Useful one... But same problem can be solved by following two checks: Graph is connected (Simple DFS) 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. answered 06 Dec '17, 23:52 3.1k●11●35 accept rate: 22%
 toggle preview community wiki:
Preview

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×551
×314
×2

question asked: 03 Jul '14, 12:06

question was seen: 3,308 times

last updated: 06 Dec '17, 23:52