Hamiltonian Graph – Paper Boy Problem

Shyam needs to distribute newspaper to all the houses while following these rules:

  • He can start from any vertex.
  • When he is on a vertex, he must distribute the newspaper.
  • You can only travel to a vertex that is connected to the current vertex by an edge.
  • You cannot visit a vertex which is already visited.

Write a program to determine whether Shyam can distribute newspaper to all the houses or not.
Note– You can only go to one vertex from the current vertex.

Input Format

  • First line: T(number of test cases)
    For Each test case –
  • First Line: Two space separated integers N and M
  • Next M lines: Two separated integers X and Y denoting an edge between X and Y

Output Format

Print “Yes” (without quotes) if Shyam can distribute newspaper to all houses else print “No” (without quotes).

Constraints
1 <= T <= 10
1 <= N <= 10`
0 <= M <= 100
1 <= X,Y <= N

Sample Input
2
3 3
1 2
2 3
1 3
3 2
1 2
2 1

Sample Output
Yes
No

Explanation

For test case 1, if Shyam start with vertex 2 then he can deliver to all houses by following path 2 -> 3 -> 1

For test case 2, there is no possible path to cover all vertices.

Solution

If you look closely and try analyzing the use cases you will come to you will come to the conclusion that what question want you to do is to find that whether this graph is connected such that you can visit all the vertex exactly ones. Ummm…. wait a minute isn’t is something like Hamiltonian graph or Hamiltonian cycle. So now you only need to find whether given input forms hamiltonian graph or cycle.

Java solution below which is using DFS –

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Bitnami