Hamiltonian Path

A Hamiltonian path, is a path in an undirected or directed graph that visits each vertex exactly once. Given an undirected graph  the task is to check if a Hamiltonian path is present in it or not.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line consists of two space separated integers N and M denoting the number of vertices and number of edges.Then in the next line are M space separated pairs u,v denoting an edge from u to v.

Output:
For each test case in a new line print 1 if a Hamiltonean path exists else print 0.

Constraints:
1<=T<=100
1<=N<=10
1<=M<=15

Example:
Input:

2
4 4
1 2 2 3 3 4 2 4
4 3
1 2 2 3 2 4
Output:
1
0

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

rakesh

Leave a Reply

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

Skip to toolbar