Algorithm Chain

The task

Given a set of non-repeating pairs (A _i , A _j ), A _i , A _j belong to the set A = {A ₁ , A ₂ , ..., A _n }. It is necessary to make a chain of maximum length according to the rule.

(A _i , A _j ) + (A _j , Ak) = (A _i , A _j , A _k ).

With the formation of this chain, any pair can be used no more than once.

Input

The input data is the adjacency matrix compiled according to this rule: C [i, j] = 1, if the set contains a pair (Ai, Aj) and C [i, j] = 0 otherwise.

Conclusion

Print the sequence of links in the longest chain in the format Ai Ak ... An.

Solution [up]

We will build all possible chains (according to the rule given in the condition) and look for among them the one that has the maximum length. To do this, use the search in depth. After building the chain, to which it is already impossible to attach a single link, compare the length of the current chain with the maximum length. If the current chain is longer, then we memorize it and consider the current chain maximum. The formal algorithm is shown below.

Formal description

  Chain ()
 1. Create an adjacency matrix for the chain.
 2. For each vertex of the graph, repeat clauses 2.1-2.4:
    2.1.  Search in depth to find a non-increasing route from the current 
         tops.
    2.2.  If the route found is longer than the maximum, then save 
         This route and consider it the maximum.
    2.3.  Find the next route for the current vertex. 
    2.4.  If the route is not found, then go to the next vertex.
 3. Print the longest route.