Hi, i am trying to solve http://www.spoj.com/problems/WORDS1/ on spoj,i came to know the problem is about checking the graph has euler path or not.

Any one please tell me how to check if a graph has euler path?

Hi, i am trying to solve http://www.spoj.com/problems/WORDS1/ on spoj,i came to know the problem is about checking the graph has euler path or not.

Any one please tell me how to check if a graph has euler path?

Check the following conditions for Euler path to exist:

- Graph should be connected
- There should be exactly one vertex with outdegree-indegree=1 (starting vertex)
- There should be exactly one vertex with indegree-outdegree=1 (final vertex)

To actually determine the euler path refer to this excellent tutorial.

Here is another excellent problem on Euler path to try.

1 Like