import java.util.*;

public class TravellingSalesman

{

private int numberOfNodes;

private Stack<Integer> stack;

public TravellingSalesman()

{

stack = new Stack<Integer>();

}

public void tsp(int adjacencyMatrix[][])

{

numberOfNodes = adjacencyMatrix[1].length - 1;

int[] visited = new int[numberOfNodes];

visited[0] = 1;

stack.push(0);

int element, dst = -1, i;

int min = Integer.MAX_VALUE;

boolean minFlag = false;

System.out.print(0 + "\t");

while (!stack.isEmpty())

{

element = stack.peek();

i = 1;

min = Integer.MAX_VALUE;

while (i <numberOfNodes)

{

if (adjacencyMatrix[element][i] > 1 && visited[i] == 0)

{

if (min > adjacencyMatrix[element][i])

{

min = adjacencyMatrix[element][i];

dst = i;

minFlag = true;

}

}

i++;

}

if (minFlag)

{

visited[dst] = 1;

stack.push(dst);

System.out.print(dst + "\t");

minFlag = false;

continue;

}

stack.pop();

}

}

public static void main(String... arg)

{

int number_of_nodes;

Scanner scanner = null;

try

{

System.out.println("Enter the number of nodes in the graph");

scanner = new Scanner(System.in);

number_of_nodes = scanner.nextInt();

int adjacency_matrix[][] = new int[number_of_nodes][number_of_nodes];

System.out.println("Enter the adjacency matrix");

for (int i = 0; i < number_of_nodes; i++)

{

for (int j = 0; j < number_of_nodes; j++)

{

adjacency_matrix[i][j] = scanner.nextInt();

}

}

for (int i = 0; i < number_of_nodes; i++)

{

for (int j = 0; j < number_of_nodes; j++)

{

if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)

{

adjacency_matrix[j][i] = 1;

}

}

}

System.out.println("the citys are visited as follows");

TravellingSalesman obj = new TravellingSalesman();

obj.tsp(adjacency_matrix);

} catch (Exception E)

{

System.out.println(E);

System.out.println("Wrong Input format");

}

scanner.close();

}

}