Neeki's blog

1521D — Nastia Plays with a Tree
By Neeki, history, 6 months ago, In English

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 isn't it correct??

submission

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

hello, i think the problem is in your code not in your algorithm because, in your code in the section that checks the first 3 steps if deg[u] or deg[i] is less than what it meant to be, you shouldn't break, you should continue, this is why it fails the second test case in test 2, in that test case 14 is connected to nodes 1 , 16 and 18, your code checks the pair 14 and 1, and because it don't met the condition No.1 it breaks out, but if it continue, it will find the pair 14 , 18.

i hope this help (this code i said doesn't work completely too, maybe there are some other problems)

→ Reply