PT07X - Vertex Cover

You are given an unweighted, undirected tree. Write a program to find a vertex set of minimum size in this tree such that each edge has as least one of its end-points in that set.


The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 100000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).


Print number of nodes in the satisfied vertex set on one line.

Example 1

1 2
1 3


The set can be {1}

Example 2

1 2
2 3


The set can be {2}

hide comments
cake_is_a_lie: 2017-03-05 14:44:08

For some reason I understood each vertex needed one neighbour in the output set. That cost me SO many WAs.

siddharth9820: 2017-02-19 09:27:54

Isnt it a straight divide and conquer problem?

sina_ss: 2017-02-14 18:03:23

it is so badihi

Last edit: 2017-02-14 18:53:24
vengatesh15: 2016-12-23 06:50:41

AC in 1 go :-)

lt: 2016-11-27 14:51:55

Greedy is failing in very particular cases, while DP is awesome! :D

Last edit: 2016-11-27 14:52:50
kartikay singh: 2016-06-30 18:05:47

Tried with dp,greedy and maximum matching ... :-D

Md. Najim Ahmed: 2016-02-15 06:33:23

Excellent practice problem. Topics: Minimum dominating set in a tree.
One should try all possible solutions => greedy , Dp, and BPM

bholagabbar: 2015-12-07 17:11:25

To solve it using Maximum matching:

1. First run a BFS where you color the child and parent with alternate colors. Here, you are basically partitioning the tree (a tree is bipartite in nature) into the 2 bipartite partitions.
2. Now, the from the undirected graph you have built, erase the entries of either the vertices with color 0 or color 1
3. And now run maximal matching on the graph left. This works because now you have the left side of the Bipartite graph, which is what you require for most matching algorithms. This did it for me

Rocker3011: 2015-08-18 23:43:24


r0bo_dart: 2015-06-24 15:03:17

This can be done using DP. But then try implementing it using Hopcroft Karp algo for Bipartite matching.

Added by:Thanh-Vy Hua
Time limit:0.194s-1.254s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Co-author Amber