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}
hide comments
vidhan_1234:
2022-10-10 11:42:50
Yes, week test case. |
|
partho_das:
2022-01-03 08:48:33
I got AC with Greedy. |
|
thang040602:
2021-05-16 19:10:01
i ACed this long ago and i just realized how weak the test set is :( |
|
princemishra:
2021-01-18 15:28:40
https://www.youtube.com/watch?v=RuNAYVTn9qM&list=PLb3g_Z8nEv1j_BC-fmZWHFe6jmU_zv-8s&index=2
|
|
std_iostream:
2020-10-10 23:33:19
Can someone please say how will be the output form for N=1? |
|
hack_010:
2020-09-03 07:17:27
@osmanay2 Answer should be 5 in your test case. My solution got accepted with that. |
|
shameek:
2020-06-16 03:49:14
2 states - the vertex number and a boolean used
|
|
kushagra_2:
2020-04-22 19:52:18
First tree dp problem :) Indeed very happy to solve... A great problem worth solving!! |
|
danos:
2020-03-21 08:20:56
13
|
|
sayamrak:
2020-03-13 21:46:14
Simple Dp on trees |
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 |