akash2504's blog

spoj — Vertex Cover
By akash2504, 11 years ago, In English

http://www.spoj.com/problems/PT07X/ Can someone help me to solve above problem? i m stuck n couldnt find any way through :(

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

Comments Comments (6)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, it's a pretty easy problem. You should maintain a queue of vertices with degree equal to 1 and add their neighbours to the answer, decrease the neighbour's neighbours' degree by 1 and add those which get degree equal to 1 to the queue.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Its a tree .... so it is bipartite. So maximum matching is the answer. As n = 100000, we can use Hopcroft–Karp Bipartite Matching. I got AC using Bipartite Matching.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I think we don't really need a matching. As you mentioned the graph is bipartite. After running a BFS or DFS the answer is the size of the part with minimum elements.

    Note: I'm not sure about the correctness of my idea. I'm not home and I can't write it now.

    Update: I'm wrong and I'm sorry for confusing you... My code

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this code doesn't work for test case 7 (1,2)(1,3)(1,4)(4,5)(4,6)(4,7)

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Actually, this is a DP problem. Let DP[i][0] be the cost of solving the subtree rooted at i when i itself is not selected, and DP[i][1] be the cost of solving the subtree rooted at i when i is selected. If we don't select i, we must select all its children, otherwise there will be edges with no selected vertex. If we select i, we can freely choose whether or not to select their children when we solve those subtrees. Then...

In the formulas above, c represents the set of children of node i. The answer we seek will be the minimum of DP[1][0] and DP[1][1], assuming we root our tree at node 1.

→ Reply