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
- First line: T(number of test cases)
ForEach test case –
- First Line: Two
space separatedintegers N and M
- Next M lines: Two separated integers X and Y denoting an edge between X and Y
Print “Yes” (without quotes) if Shyam can distribute newspaper to all houses else print “No” (without quotes).
1 <= T <= 10
1 <= N <= 10`
0 <= M <= 100
1 <= X,Y <= N
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.
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 –