We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Let's re-word this question :
You're given a graph as input (in the form of pairs of vertices; every pair represents an edge).
"Your task is to mark as small number of vertices as possible, such that, the maximum distance between two unmarked vertices is less than or equal to K."
The above sentence says you need to mark (assume, mark = delete a vertex) so that the remaining number of vertices have atmost K length between them. In other words : find the minimum number of vertices you need to remove so that the remaining tree has path <= K between the vertices.
Hint : Use floyd warshall algorithm.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Far Vertices
You are viewing a single comment's thread. Return to all comments →
Let's re-word this question : You're given a graph as input (in the form of pairs of vertices; every pair represents an edge).
"Your task is to mark as small number of vertices as possible, such that, the maximum distance between two unmarked vertices is less than or equal to K."
The above sentence says you need to mark (assume, mark = delete a vertex) so that the remaining number of vertices have atmost K length between them. In other words : find the minimum number of vertices you need to remove so that the remaining tree has path <= K between the vertices. Hint : Use floyd warshall algorithm.