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.

Input

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).

Output

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

Example 1

Input:
3
1 2
1 3

Output:
1

Explanation:
The set can be {1}

Example 2

Input:
3
1 2
2 3

Output:
1

Explanation:
The set can be {2}

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

hide comments
2017-02-19 09:27:54
Isnt it a straight divide and conquer problem?
2017-02-14 18:03:23
it is so badihi

Last edit: 2017-02-14 18:53:24
2016-12-23 06:50:41
AC in 1 go :-)
2016-11-27 14:51:55 lt
Greedy is failing in very particular cases, while DP is awesome! :D

Last edit: 2016-11-27 14:52:50
2016-06-30 18:05:47 kartikay singh
Tried with dp,greedy and maximum matching ... :-D
2016-02-15 06:33:23 Md. Najim Ahmed
Excellent practice problem. Topics: Minimum dominating set in a tree.
One should try all possible solutions => greedy , Dp, and BPM
2015-12-07 17:11:25 bholagabbar
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
2015-08-18 23:43:24 Rocker3011
greedy!
2015-06-24 15:03:17
This can be done using DP. But then try implementing it using Hopcroft Karp algo for Bipartite matching.
2015-04-15 04:46:11 GAURAV CHANDEL
can be solved using dp
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.