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

×

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; }

asked 03 Jul '14, 12:06

trek's gravatar image

2★trek
32741218
accept rate: 0%

edited 03 Jul '14, 12:40


nice one!!

link

answered 03 Jul '14, 16:04

suryanit's gravatar image

4★suryanit
11134
accept rate: 0%

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

link

answered 06 Dec, 23:21

rahuljain1310's gravatar image

0★rahuljain1310
1
accept rate: 0%

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

link

answered 06 Dec, 23:22

rahuljain1310's gravatar image

0★rahuljain1310
1
accept rate: 0%

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.

link

answered 06 Dec, 23:52

taran_1407's gravatar image

5★taran_1407
2.2k622
accept rate: 22%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×474
×310
×2

question asked: 03 Jul '14, 12:06

question was seen: 3,198 times

last updated: 06 Dec, 23:52