Infoshoc's blog

Eulerian path problem
By Infoshoc, 9 years ago, In English

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!

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

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

508D - Tanya and Password

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

    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"!

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

      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 with dfs and similar, and graphs certainly.

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

        Yes. You are definitely right. Probably this is the reason why it is so hard for me to find problem of searching Eulerian path...

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

can you give me any link for learning Eulerian path algorithm

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

723E — One-Way Reform

→ Reply