70. HAMILTONIAN CYCLE PROBLEM

//HAMILTONIAN CYCLE PROBLEM
import java.io.*;
public class Hamiltonian
{
static int [][] G;
static int [] x;
static int n;
static boolean found = false;
public static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException
{
System.out.println("\t\t\t\tHamiltonian Cycle");
System.out.print("\nEnter the number of the vertices: ");
n = Integer.parseInt(br.readLine());
G = new int[n+1][n+1];
x = new int[n+1];

System.out.print("\nIf edge between the following vertices enter 1 else 0:\n");
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if((i!=j)&&(i<j))
{
System.out.print(i+" and "+j+": ");
G[j][i]=G[i][j] = Integer.parseInt(br.readLine());
}
if(i==j)
G[i][j]=0;
}
for(int i=1;i<=n;i++)
x[i] = 0;
x[1] = 1;
System.out.println("\nSolution:");
Hamiltonian (2);

if (found == false)
System.out.println("No Solution possible!");
}
static void Hamiltonian(int k)
{
while(true)
{
NextValue(k);
if(x[k] == 0)
return;
if(k == n)
{
for(int i=1; i<=k;i++)
System.out.print(x[i]+" ");
System.out.println();
found = true;
return;
}
else
Hamiltonian(k+1);
}
}

static void NextValue(int k)
{
while(true)
{
x[k] = (x[k]+1)%(n+1);
if(x[k] == 0)
return;
if(G[x[k-1]][x[k]] !=0)
{
int j;
for(j = 1; j<k; j++)
if(x[k] == x[j])
break;
if(j==k)
if( (k<n) || ( (k==n) && G[x[n]][x[1]] != 0 ) )
return;
}
}
}
}