Biconnected Graph

How do you find out whether an 开发者_StackOverflowundirected graph is Biconnected or not using its depth first search traversal. Is there any other way than traversing the whole graph to find disconnected pieces of the graph.

You calculate the low(v) for every vertex in linear time (i.e. during the execution of the DFS). And there exists a bridge (i.e. an edge whose removal will disconnect the graph ==> not biconnected) iff there's a non-root vertex whose low value is itself OR if the root has more than one child.

It's explained here on point 5.2 http://www.cse.ohio-state.edu/~lai/780/graph.pdf

I have no answer to this, but my gut feeling would suggest that you would have to do the depth first search traversal as the biconnected property of the graph is a property of the whole graph and not any subset of the graph.