gfonn's blog

Help with this problem!
By gfonn, 8 years ago, In English

Hi everyone! I can't solve this problem, can you help me please?

Statement:

Given a list of words, you have to find an order in which a word A can be before to word B only if the last letter of A is the same that the first letter of B. This order must be circular, like this:

(LEFT: Given words. RIGHT: A possible ordering of the words)

Input: First line, the quantity of words N (1 <= N <= 9000). Next N lines have the words (one word per line). Lenght of each word don't exceed 6:

6
arbol
orden
susana
otro
listo
nexos

Output: If it's possible to make the circular ordering, print N lines with the words ordered (as the ordering is circular, you can start listing them with any word). If it's impossible, print "Impossible"

susana
arbol
listo
otro
orden
nexos

FULL STATEMENT (IN SPANISH)

The first thing I know is that for finding the ordering you only need two letters (first and last of each word). I was thinking in Hamiltonian Cycle, but the input is too big.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Hint: it is hard to find a Hamiltonian cycle but easy to find Eulerian cycle. So, construct a graph so that you have to do the latter.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Construct a graph such that a->b exist if last character of a is same as first character of b .try finding a cycle of length N

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's almost like this problem.

You can find many solutions on google, like this one.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, it's very similar! Nice one!

    → Reply