Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

lantrungseo's blog

By lantrungseo, history, 5 months ago, In English,

I don't know whether this idea has been discussed somewhere before, but I find it quite interesting.


Summary of the problem: Given a tree find a largest set of edges such that no two edges share an endpoint (maximum matching), or to find minimal set of nodes such that each node outside the set must be adjacent to at least one node in the set (minimum vertex cover).

Usual algorithm: Dynamic programming (refer to this blog : Codeforces blog)

My (maybe-wrong) greedy idea:

  1. Root the tree at arbitrary node, let say node 1.

  2. Find the distances of other nodes to node 1 (means find the height of each node). Sort the nodes according to their distances to node 1 (means sort by height).

  3. Go from the node with greatest height, if this node is not used and its parent is not used, then we match this node with its parent.

My correct submission to above SPOJ problem:

Could anyone prove or disprove it? Thanks in advanced!

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

5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by lantrungseo (previous revision, new revision, compare).