Given an undirected graph, determine if there is a path from one node to another.

Input. The input consists of one or more graph specifications. Each specification consists of three parts. The first part is a line with the source and target nodes, separated by one space. The second part is a line consisting of integer n, the number of edges in the graph. The third part consists of n edges. Each edge is given on a line and consists of a pair of nodes separated by spaces. All nodes are integers.

Output. For each graph, output true when there is a path between the source and target nodes, output false otherwise.

# Check your solution online

Before you read our solution, try to solve the problem on your own. Remember that practice makes perfect.

#### Click here to check your solution online at The Book of Problems.

2018-07-09 The Book of Problems currently supports Ruby, Python, Elixir, Java, C, OCaml, and now C++!

# O.K. solution

Apply Breadth-first Search.

# Implementation of O.K. solution

Here is a Ruby implementation.

# Solution

Apply Bidirectional Search.

# Implementation of solution

Here is a Ruby implementation.

# Want to read more?

I love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.