Всем привет! Однажды я изучал Эйлеров Цикл и алгоритм его нахождения, но не нашел соответствующей задачи онлайн. Сейчас я решаю другую задачу, в которой поиск Эйлерова цикла только часть задания и хочу проверить мои умения в реализации алгоритма на более простых задачах.
Вопрос: кто-то может мне посоветовать задачу связанную с поиском Эйлерового цикла?
Зарание спасибо.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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 pathis 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, andgraphscertainly.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