
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
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 –