# How to determine whether there is exactly one simple path between two nodes in a graph

Given an undirected sparse graph G and a list of queries (each query consisting of two nodes), how to determine if there exists exactly one simple path between them (for each query) ? I have a (trivial) solution based on a breadth-first search (for each query the complexity would be O(V+E)) but is there a more efficient way to answer the queries?

You don't have to find the actual simple path, just answer each query with a True/False answer.

This question was asked as part of the Latin American regional competition of the 2011 ACM International Collegiate Programming Contest.

• It might help to compute the decomposition of your graph into biconnected components ( en.wikipedia.org/wiki/Biconnected_component ) in linear time. If you have a query where the two vertices come from the same biconnected component (and this has > 2 vertices), then there are at least two simple paths (by definition). If the query vertices come from different biconnected components, you might speed up your procedure by searching in the block tree instead of in the original graph. Depending on the nr of biconnected components vs vertices, the speedup might be significant. Nov 7 '11 at 11:04
• This smells like homework. Nov 7 '11 at 11:22
• I agree, it smells homeworky. Since there are so few constraints on the problem, there are a number of obvious options to pursue. Nov 7 '11 at 17:11
• I think that a problem in a programming contest is also off-topic in a similar way that an exercise in a textbook is off-topic. Also please reveal the source from the beginning (although I appreciate that you revealed the source eventually). Nov 7 '11 at 20:46
• @jplot: Please edit the question to include the source; do not assume that people always read all comments. Nov 8 '11 at 6:53