Biconnected Component in a graph

Правка en1, от gsmcoder97, 2016-06-09 12:42:29
[This](http://mirror.codeforces.com/contest/652/problem/E) problem is a very interesting one. 
We have to check whether there exists some path between two nodes in a graph such that that path contains at least one edge with value 1.
After spending a lot of time, I had to see the editorial and was intrigued by the solution and the explanation.
We assume that the two points are present in some two biconnected components of the same graph(Lets say A and B).
After decomposing the graph into biconnected components we apply dfs from component A to component B and find whether the path contains at least one.
If we were not going to use this approach, then we would have to use multiple dfs traversals; perhaps including recursion.
I found this use of biconnected components really interesting.
Does anyone have any collection or references of questions that I can practice on biconnected components in a graph(perhaps constructing a DAG on them etc.)
Thank You
Теги biconnected-graph, biconnected-components

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский gsmcoder97 2016-06-09 12:42:29 1014 Initial revision (published)