1521D — Nastia Plays with a Tree

Revision en2, by Mhn_Neek, 2024-06-29 16:51:36

I tried a greedy solution for this problem:
1. If there exist a pair of adjacent vertices like $$$(u,v)$$$ such that $$$deg(u)\geq3$$$ and $$$deg(v)\geq3$$$, then remove the edge between $$$u$$$ and $$$v$$$.
2. Then, if there exist a pair of adjacent vertices like $$$(u,v)$$$ such that $$$deg(u)\geq3$$$ and $$$deg(v)\geq2$$$, then remove the edge between $$$u$$$ and $$$v$$$.
3. Then, if there exist a pair of adjacent vertices like $$$(u,v)$$$ such that $$$deg(u)\geq3$$$ and $$$deg(v)\geq1$$$, then remove the edge between $$$u$$$ and $$$v$$$.
At last, I add edges between the leaves of different components .
Why it is not correct??

submission

Tags 1521d, graph, problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Mhn_Neek 2024-06-29 16:53:13 7 Tiny change: 'br>\nWhy it is not correct?' -> 'br>\nWhy isn't it correct?'
en2 English Mhn_Neek 2024-06-29 16:51:36 82 Tiny change: ' $deg(u)>=3$ and $de' -> ' $deg(u)>=\geq3$ and $de' (published)
en1 English Mhn_Neek 2024-06-29 16:46:33 722 Initial revision (saved to drafts)