Connection Status:
Competition Arena > HamiltonianPathsInGraph

HamiltonianPathsInGraph

SRM 733 · 2018-04-13 · by ltdtl

SRM 733 · 2018-04-13 · by ltdtl · Graph Theory, Greedy
Class Name: HamiltonianPathsInGraph
Return Type: int[]
Method Name: findPath
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{".+",
 "-."}
Returns: {0, 1 }

There is a unique Hamiltonian path in this example.

1)
{".++",
 "-.+",
 "--."}
Returns: {0, 1, 2 }

There is a unique Hamiltonian path in this example.

2)
{".--+",
 "+.+-",
 "+-.-",
 "-++."}
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).

3)
{".+-+",
 "-.+-",
 "+-.-",
 "-++."}
Returns: {3, 2, 0, 1 }
4)
{".++--",
 "-.-++",
 "-+.+-",
 "+--.+",
 "+-+-."}
Returns: {3, 0, 2, 1, 4 }

Submissions are judged against all 209 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HamiltonianPathsInGraph with a public method vector<int> findPath(vector<string> X) · 209 test cases · 2 s / 256 MB per case

Submitting as anonymous