<p>Ok, now that you've revealed the motivation: there is exactly one simple path between two nodes iff there is a path in which every edge is a bridge of the graph. So find all the bridges (standard linear time by depth first search) and compute the connected components of the subgraph they form. Two vertices have a unique simple path iff they belong to the same component.</p>

CC BY-SA 3.0
2011-11-08T04:09:15.180Z
Oops; your answer was much simpler and faster than mine!
Andrew D. King
CC BY-SA 3.0
2011-11-08T03:54:58.663Z
2011-11-08T03:54:58.663Z
David Eppstein
<p>Given an undirected sparse graph G and a list of queries (each query consisting of two nodes), how to determine if there exists <em>exactly one</em> 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?</p>

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

<p>This question was asked as part of the Latin American regional competition of the 2011 <a href="http://en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest" rel="nofollow">ACM International Collegiate Programming Contest</a>.</p>

CC BY-SA 3.0
2011-11-07T11:04:36.797Z
It might help to compute the decomposition of your graph into biconnected components ( http://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.
Bart Jansen
CC BY-SA 3.0
2011-11-07T11:22:45.993Z
This smells like homework.
Jeffε
CC BY-SA 3.0
2011-11-07T17:11:11.030Z
I agree, it smells homeworky. Since there are so few constraints on the problem, there are a number of obvious options to pursue.
Josephine Moeller
CC BY-SA 3.0
2011-11-07T20:14:37.193Z
It's not homework. This question arose in one of the problems of last saturday's icpc contest in south america. It seemed to me that  the solution was well known in graph theory, that's why I asked.
jplot
CC BY-SA 3.0
2011-11-07T20:46:25.080Z
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).
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-08T06:53:28.833Z
@jplot: Please edit the question to include the source; do not assume that people always read all comments.
Jukka Suomela
CC BY-SA 3.0
2011-11-08T21:49:38.303Z
@jplot, even if it is not a homework, it is of that level, i.e. it is not a research level question. For such questions please use Math.SE.
Kaveh
<ds.algorithms><graph-theory><graph-algorithms>
How to determine whether there is exactly one simple path between two nodes in a graph
jplot
# How to determine whether there is exactly one simple path between two nodes in a graph

(Asked by: username_0 on 2011-11-07)

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](http://en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest).

**Tags:** ds.algorithms, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: It might help to compute the decomposition of your graph into biconnected components ( http://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.  
> **username_2**: This smells like homework.  
> **username_3**: I agree, it smells homeworky. Since there are so few constraints on the problem, there are a number of obvious options to pursue.  
> **username_0**: It's not homework. This question arose in one of the problems of last saturday's icpc contest in south america. It seemed to me that  the solution was well known in graph theory, that's why I asked.  
> **username_4**: 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).  
> **username_5**: @jplot: Please edit the question to include the source; do not assume that people always read all comments.  
> **username_6**: @jplot, even if it is not a homework, it is of that level, i.e. it is not a research level question. For such questions please use Math.SE.  

---

## 1 answers

### Answer by username_7 on 2011-11-08. Score: 14 | Accepted answer

Ok, now that you've revealed the motivation: there is exactly one simple path between two nodes iff there is a path in which every edge is a bridge of the graph. So find all the bridges (standard linear time by depth first search) and compute the connected components of the subgraph they form. Two vertices have a unique simple path iff they belong to the same component.

> **Comments:**
> **username_8**: Oops; your answer was much simpler and faster than mine!  

---

