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
|
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 |
|
osmanay2:
2020-02-10 23:07:22
Test your solution with this case:
|
|
scolar_fuad:
2019-12-01 05:26:35
Minimum vertex cover dp problem
|
|
mzuenni:
2019-11-29 12:32:36
just solve it greedy: take the neighbour of a leaf and remove it. |
| 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 |
RSS