Hello, everyone! Once, I was learning about Eulerian path and algorithm of it's founding, but did not find then the appropriate problem on online judges. Now I am solving another problem, where finding Eulerian cycle is just a part of task, and I would like to check my skills in realization of the algorithm on some simpler problem.
The question is: can anyone recommend me problems connected with finding Eulerian path?
Thank you in advance!
508D - Tanya and Password
Thanks! It really helped me! Do you know any other tasks on this topic? It is very strange, that this problem is not tagged with "Eulerian path"!
You may misunderstand the meaning of tags.
Eulerian path
is too specific to be a tag. In fact, the general algorithm to find Eulerian path is a kind of DFS. So this is tagged withdfs and similar
, andgraphs
certainly.Yes. You are definitely right. Probably this is the reason why it is so hard for me to find problem of searching Eulerian path...
can you give me any link for learning Eulerian path algorithm
For me, the most useful one was Wikipedia
But as far as I understood, in order to use this algorithm, you have to check, if there is Eulerian path (using properties: for undirected graph — the graph should be connected (and probably has vertices without edges) and <= 2 vertices should have odd degree. for directed graph — the graph should be strongly connected, and all vertexes but two has in degree == out degree and two have degrees differ by one for path, and for cycle all vertices should have the same in and out degree.
And if you are using algo for searching cycle in order to find path, you should add edge and afterwards extract it.
Prove me someone if I was wrong, please! And tell me if someone using simpler methods?
723E — One-Way Reform