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.

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

2017-10-08 The Book of Problems currently supports Ruby, Python and now Elixir. More languages will come soon. If there is a language you’d like to use, drop me a line in the comments section.

# Implementation of O.K. solution

Here is a Ruby implementation.

# Solution

Apply Bidirectional Search.

# Implementation of solution

Here is a Ruby implementation.