gsmcoder97's blog

By gsmcoder97, history, 9 years ago, In English
[This](http://codeforces.net/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
  • Vote: I like it
  • 0
  • Vote: I do not like it