HamiltonianPathsInGraph | Topcoder Archive

Problem Statement

Consider a directed graph G on n vertices (labeled 0, 1, 2, ..., n-1) with exactly n*(n-1)/2 edges: for every pair of distinct vertices (i, j) there is either an edge from i to j or an edge from j to i, but not both. (Hence, if we ignore the orientation of edges, G is a complete graph.)

You are given the adjacency matrix of G. More precisely, you are given a String[] X with n elements, each containing n characters. For each pair of distinct i and j, X[i][j] is either '+' (denoting that G contains an edge from i to j) or '-' (denoting that G does not contain this edge). On the diagonal we have X[i][i] = '.' denoting that there are no self-loops in G.

A Hamiltonian path in G is a path of length n that contains each vertex of G exactly once. It can be shown that a graph G that has the properties described above must always contain at least one Hamiltonian path. Find and return any Hamiltonian path in the given graph G. More precisely, return a int[] with n elements: the numbers of vertices in the order in which they lie on your Hamiltonian path.

Definition

Class:: HamiltonianPathsInGraph
Method:: findPath
Parameters:: String[]
Returns:: int[]
Method signature:: int[] findPath(String[] X)
(be sure your method is public)

Constraints

n will be between 2 and 100, inclusive.
X will contain exactly n elements.
Each element of X will contain exactly n characters.
For each i, X[i][i] will be '.'.
For each i and j such that i != j, X[i][j] will be either '+' or '-'.
For each i and j such that i != j, X[i][j] will be different from X[j][i].

Examples

```
{".+",
 "-."}
```
```
Returns: {0, 1 }
```
There is a unique Hamiltonian path in this example.
```
{".++",
 "-.+",
 "--."}
```
```
Returns: {0, 1, 2 }
```
There is a unique Hamiltonian path in this example.
```
{".--+",
 "+.+-",
 "+-.-",
 "-++."}
```
```
Returns: {3, 1, 2, 0 }
```
There are multiple correct answers. Any of the following is a correct answer. {0, 3, 1, 2} {1, 0, 3, 2} {1, 2, 0, 3} {2, 0, 3, 1} {3, 1, 2, 0} For example, {0, 3, 1, 2} is a correct answer because G contains the edges (0, 3), (3, 1), and (1, 2).

{".+-+",
 "-.+-",
 "+-.-",
 "-++."}

Returns: {3, 2, 0, 1 }

{".++--",
 "-.-++",
 "-+.+-",
 "+--.+",
 "+-+-."}

Returns: {3, 0, 2, 1, 4 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.