holmes_324's blog

Need Help in a Graph Problem

By holmes_324, history, 18 months ago, In English

I didn't understand what paint(v) means. Can someone please explain me. Also I didn't understand the editorial solution of this problem. Can't we just count unconnected black ans white components and output min of them Problem link Thanks in advance!

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

»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

paint(v) means that you should choose a vertex (v) and color all vertices (u) which have the same color as (v) and at the same time there is no vertex that has another color in the simple path between (v) and (u).

→ Reply
»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Your solution which is counting unconnected black and white components and output the minimum of them should be true.

→ Reply
»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

The editorial is just explaining how you can count those unconnected black and white components in an efficent way (compressing the tree and finding the diameter).

→ Reply