| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3947 |
| 2 | jiangly | 3734 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | ecnerwala | 3581 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | ksun48 | 3479 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 162 |
| 2 | maomao90 | 160 |
| 3 | nor | 156 |
| 4 | cry | 155 |
| 4 | adamant | 155 |
| 4 | atcoder_official | 155 |
| 4 | -is-this-fft- | 155 |
| 8 | maroonrk | 153 |
| 9 | SecondThread | 147 |
| 10 | Petr | 146 |
Given a undirected graph with $$$N (N \leq 100)$$$ vertices, $$$M (M \leq N * (N + 1) / 2)$$$ edges (there can be edge connect a vertex with itself but all edges are distinct).
Find the number of minimum paths that every edge is in exactly 1 path.
Thanks.
UPD: I just realized it is sum of (odd vertices / 2) for every connected component (and some special case like m = 0, odd vertices = 0).
just find Eilerev way ? or am i wrong ?
Sorry I don't understand what you mean. Could you elaborate it a bit?
As I understand it, a non-weighted graph is given and we want to visit all the edges exactly once, but exactly this is done by the algorithm of the eleree path, there is a theorem when it is possible to traverse all the edges once.
So what happen when there is > 2 odd degree vertex that you cannot fit every vertices into 1 path. Then how many paths? And what if after finishing 1 path you make the graph unconnected ... etc.
Ahhh, I just realized your question, sorry
Auto comment: topic has been updated by Libraion (previous revision, new revision, compare).