I need to select maximum vertices in a graph such that the distance between any two selected vertices is less than the given limit? distance between adjacent nodes is 1. Input n,d meaning number of nodes and the limit d, n-1 lines follows denoting edges. Example 6 5 2 1 2 3 4 2 1 6 5 6
Output 5 As all 5 vertices can be selected within the range d
Seems, your graph is a tree, because you wrote there n-1 edges. If so, there exists simple algo O(n^2), for every node run BFS no longer distance than
d
. calculate number of nodes.And, I belive that, there must exists linear solution.
3 1
1 2
2 3
in this case your output is 3 but the answer is 2
Thanks, yea, I didn't read problem carefully.
There required distance for each vertex in the set must
less
thanlimit d
.if n<=20 , then you can solve it by dp + bitmask
CAN YOU SHARE LINK TO PROBLEM ?
If this graph is a tree, there exists O(N^2) solution.
In the graph for every pair of vertexes exist single path.
Think that, if we build solution, there exist a pair of vertexes where distance is maximum, select middle of these vertexes, for selected vertex, distance from it to any other vertexes in the set less or equal
(1+d)/2
.dp[i][j][k] -- number of nodes in subtree rooted at node i , using jth of its child , upto a depth of of k.. For every node , we will have the number of nodes in each child subtree upto different heights of different nodes..