SPOJ.com - Problem PT07X

PT07X - Vertex Cover

#tree

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}

Submit solution!

hide comments

< Previous 1 2 3 4 5 Next >

	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 greedy!
	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.
	GAURAV CHANDEL: 2015-04-15 04:46:11 can be solved using dp

Submit solution!

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