Eulerian path, arranging words

Question

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm'' can be followed by the word motorola''.

Eg: skenzo logicboxes orderbox

ans: ordering possible

I know this problem is related to Eulerian path. But I am unable to implement it. Can someone tell me how it can be implemented. Means how should I make graph and which nodes must be connected. I know I have to use adjacency matrix but which nodes must be connected.

Answer 1

WORDS1, if I remember correctly. Contrary to some others, I agree that what you want is an Eulerian path, not a Hamiltonian. In the resulting graph, the words are the edges (from first letter to last) and the letters (conveniently only lower case letters from 'a' to 'z' in ASCII) the vertices.

Actually, what you want is not the path itself, you only want to know if there is one. So you need necessary and sufficient conditions on a graph for the existence of an Eulerian path.

Evidently, for such a path to exist, the graph has to be connected. You can determine that efficiently with a union find.
Then, the existence of such a path imposes conditions on the in- and outdegrees of the vertices. If you formulate these conditions correctly, a) they are necessary and sufficient, b) they are easy to check.

It's more fun to find the conditions yourself, but you could also find them in the wikipedia article about Eulerian paths.