Does this question needs Hamilton Path or Euler Path. In my opinion it needs Hamilton Path but then how can we solve this ???

Were you able to solve this? I am trying to solve it with euler path but it is always giving ‘wa’! Can you help?

I think that while this may be solved using a Hamiltonian Path solver, this doesn’t necessarily need one.

In other words, you can reduce this problem to Hamiltonian Path, but you cannot reduce Hamiltonian Path to this problem (clearly: for any general graph, it may not be possible to find words of length <= 1000 from only 26 letters, which induce the same graph).

For another example:

Graph colorability is a “difficult” problem.

Consider the problem of being given N time intervals in which there are meetings, and you need to find the minimum number of rooms to conduct those meetings such that they do not overlap.

This can obviously be solved using graph colorability - however, there is also a very simple greedy solution for it.

In general, try to prove that an NP-Hard problem reduces to a given problem, before declaring it impossible.

Eulerian is the right approach.

@darkshv22: Either you are not working on the right graph or you didn’t check **all** conditions for an Eulerian path.

thanks for sharing views

For More Information Please Visit :

packers and movers in mumbai

packers and movers in delhi

packers and movers in bangalore

Euler path. The words are edges and you need to take each of them exactly once; think, what are the vertices?

Also, watch out for multiple edges.