# HackerRank Far Vertices problem solution

In this HackerRank Far Vertices problem solution we have given a tree that has N vertices and N-1 edges. Your task is to mark as small a number of vertices as possible, such that, the maximum distance between two unmarked vertices is less than or equal to K. Output this value. Distance between two vertices i and j is defined as the minimum number of edges you have to pass in order to reach vertex I from vertex j.

## Problem solution in Python.

```n, k = [int(a) for a in input().split(" ")]
count = 0

class Node(object):
def __init__(self):
self.neighbors = []
self.marked = False

def set_neighbor(self, neighbor):
self.neighbors.append(neighbor)

def mark_dfs(self, depth, root = False):
global count
self.marked = True
count += 1
if depth == 0:
children = len(self.neighbors) - 1
if not root:
return children
return min(children, 1)
num_children = 0
for neighbor in self.neighbors:
if not neighbor.marked:
mc = neighbor.mark_dfs(depth-1)
if root:
num_children = max(num_children,mc)
else:
num_children += mc
return num_children

nodes = []
for i in range(n):
node = Node()
nodes.append(node)

def unmark_all():
for node in nodes:
node.marked = False

for i in range(n - 1):
u, v = [int(a) - 1 for a in input().split(" ")]
nodes[u].set_neighbor(nodes[v])
nodes[v].set_neighbor(nodes[u])
max_count = 0
for node in nodes:
c = node.mark_dfs(k // 2, True)
if k % 2 == 1:
count += c
if count > max_count:
max_count = count
unmark_all()
count = 0
print(n - max_count)
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

static int[][] dist;
static int[] parent;
static ArrayList<ArrayList<Integer>> neighbours;
/*
* Complete the farVertices function below.
*/
static int farVertices(int n, int k, int[][] edges) {
neighbours = new ArrayList<ArrayList<Integer>>();

int fr, to;
parent = new int[n];
dist = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], -1);
dist[i][i] = 0;
parent[i] = -1;
}
for (int[] edge : edges) {
fr = edge[0] - 1;
to = edge[1] - 1;
dist[fr][to] = 1;
dist[to][fr] = 1;
}
parent[0] = -2;
setParents(0);
// System.out.println(Arrays.toString(parent));
// return -2;

int p = -1;
for (int i = 0; i < n; i++) {
p = parent[i];
int d = 1;
while (p != -1 && p != -2) {
dist[p][i] = d;
dist[i][p] = d;
d += 1;
p = parent[p];
}
}
//printTree(0);

int max = 0, num = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (distance(i, j) == k) {
if ((num = count(i,j,n,k)) > max) {
max = num;
}
/*
* r += rrow[i] ? 0 : 1; c += rcol[j] ? 0 : 1; rrow[i] = true; rcol[j] = true;
*/
}
}
}
/*
* System.out.println("max = " + max); System.out.println("maxi = " + maxi);
* System.out.println("maxj = " + maxj); print(dist);
*/
return max == 0 ? 0 : n-max;

}
static int count(int i, int j, int n, int k) {
int total = 0;
for (int m=0; m<n; m++) {
if (distance(m,i) <= k && distance(m,j) <= k) {
total += 1;
}
}
}
static int distance(int fr, int to) {
if (dist[fr][to] != -1)
return dist[fr][to];

int p = parent[fr];
int d = 1;
while (p != -2 && dist[p][to] == -1) {
d += 1;
p = parent[p];
}
dist[fr][to] = d + dist[p][to];
dist[to][fr] = dist[fr][to];
return dist[fr][to];
}
private static void setParents(int i) {
ArrayList<Integer> tocheck = new ArrayList<Integer>();
for (int child : neighbours.get(i)) {
if (parent[child] == -1) {
parent[child] = i;
}
}
for (int child : tocheck) {
setParents(child);
}
}
private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nk = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

int n = Integer.parseInt(nk[0]);

int k = Integer.parseInt(nk[1]);

int[][] edges = new int[n-1][2];

for (int edgesRowItr = 0; edgesRowItr < n-1; edgesRowItr++) {
String[] edgesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

for (int edgesColumnItr = 0; edgesColumnItr < 2; edgesColumnItr++) {
int edgesItem = Integer.parseInt(edgesRowItems[edgesColumnItr]);
edges[edgesRowItr][edgesColumnItr] = edgesItem;
}
}

int result = farVertices(n, k, edges);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};

const double inf = 1.0e20;

vector <int> g[128];
int n, k, mem[128][128];

void dfs(int a, int d, int f = 0) {
int* v = mem[a], t[128];
for (int i = 0; i <= k; ++i) v[i] = 1;
if (d > 0)
for (vector <int>::const_iterator it = g[a].begin(), ie = g[a].end(); it != ie; ++it)
if (*it != f) {
dfs(*it, d - 1, a);
int* p = mem[*it];
for (int i = 0; i <= d; ++i) t[i] = v[i];
for (int i = d; i >= 0; --i) {
for (int j = 0, u; j < d && i + 1 + j <= k; ++j)
t[u = max(i, 1 + j)] = max(t[u], v[i] + p[j]);
}
for (int i = 0; i <= d; ++i) v[i] = t[i];
}
// for (int i = 1; i <= k; ++i) v[i] = max(v[i], v[i - 1]);
}

int main(void) {
for (int id = 1; 2 == scanf("%d %d", &n, &k); ++id) {
for (int i = 1; i <= n; ++i) g[i].clear();
for (int i = 1, a, b; i < n && 2 == scanf("%d %d", &a, &b); ++i)
g[a].push_back(b), g[b].push_back(a);
int best = 0;
for (int i = 1; i <= n; ++i) {
dfs(i, k);
// best = max(best, mem[i][k]);
for (int j = 0; j <= k; ++j) best = max(best, mem[i][j]);
}
printf("%d\n", n - best);
}
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 102

char** split_string(char*);

/*
* Complete the farVertices function below.
*/
struct edge{
int from;
int to;
};

int farVertices(int n, int k, int** edges) {
struct edge sortedge[2*(n - 1)];
for(int i = 0; i < n - 1; i++){
sortedge[2*i].from = edges[i][0] - 1;
sortedge[2*i].to = edges[i][1] - 1;
sortedge[2*i + 1].from = edges[i][1] - 1;
sortedge[2*i + 1].to = edges[i][0] - 1;
}

for(int i = 0; i < 2*(n - 1); i++){
int curr = i;
while(curr > 0){
int next = (curr - 1)/2;
if(sortedge[curr].from > sortedge[next].from){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}

for(int i = 2*n - 3; i >= 0; i--){
struct edge temp = sortedge[0];
sortedge[0] = sortedge[i];
sortedge[i] = temp;

int curr = 0;
while (true) {
int next = curr;
if(2*curr + 1 < i && sortedge[2*curr + 1].from > sortedge[next].from){
next = 2*curr + 1;
}
if(2*curr + 2 < i && sortedge[2*curr + 2].from > sortedge[next].from){
next = 2*curr + 2;
}
if(next != curr){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}

int edgebounds[n + 1];
edgebounds[0] = 0;
for(int i = 0; i < n; i++){
int index = edgebounds[i];
while(index < 2*n - 2 && sortedge[index].from == i){
index++;
}
edgebounds[i + 1] = index;
}

int parentlist[n];
int *childrenlist[n];
int numchildren[n];
for(int i = 0; i < n; i++){
parentlist[i] = -2;
childrenlist[i] = NULL;
numchildren[i] = 0;
}

int parentqueue[n];
int queuesize = 1;
parentqueue[0] = 0;
int queuedone = 0;
parentlist[0] = -1;

while(queuedone < queuesize){
int currnode = parentqueue[queuedone];
for(int i = edgebounds[currnode]; i < edgebounds[currnode + 1]; i++){
int nextnode = sortedge[i].to;
if(parentlist[nextnode] == -2){
parentlist[nextnode] = currnode;
queuesize++;
parentqueue[queuesize - 1] = nextnode;
numchildren[currnode]++;
childrenlist[currnode] = realloc(childrenlist[currnode], numchildren[currnode]*sizeof(int));
childrenlist[currnode][numchildren[currnode] - 1] = nextnode;
}
}
queuedone++;
}

int bestsub[n][k + 1];//bestsub[i][j] = size of largest subtree rooted at i of depth j and diam <= k

for(int i = n - 1; i >= 0; i--){
int currnode = parentqueue[i];
for(int l = 0; l <= k; l++){
bestsub[currnode][l] = 1;
}
for(int j = 0; j < numchildren[currnode]; j++){
int childnode = childrenlist[currnode][j];
int check = bestsub[childnode][k - 1] + 1;
bestsub[currnode][k] = (check > bestsub[currnode][k]? check : bestsub[currnode][k]);
for(int l = k - 1; 2*l > k; l--){
int altl = k - l;
check = bestsub[currnode][l] + bestsub[childnode][altl - 1];
bestsub[currnode][l] = (check > bestsub[currnode][l]? check : bestsub[currnode][l]);

check = bestsub[currnode][altl] + bestsub[childnode][l - 1];
bestsub[currnode][l] = (check > bestsub[currnode][l]? check : bestsub[currnode][l]);
}
for(int l = k/2; l > 0; l--){
bestsub[currnode][l] += bestsub[childnode][l - 1];
}
}
}

int max = 1;
for(int i = 0; i < n; i++){
printf("%d:\t", i);
for(int j = 0; j <= k; j++){
printf("%d %d\t", j, bestsub[i][j]);
max = (bestsub[i][j] > max? bestsub[i][j] : max);
}
printf("\n");
}
return n - max;
}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

char* n_endptr;
char* n_str = nk[0];
int n = strtol(n_str, &n_endptr, 10);

if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

char* k_endptr;
char* k_str = nk[1];
int k = strtol(k_str, &k_endptr, 10);

if (k_endptr == k_str || *k_endptr != '\0') { exit(EXIT_FAILURE); }

int** edges = malloc((n-1) * sizeof(int*));

for (int edges_row_itr = 0; edges_row_itr < n-1; edges_row_itr++) {
*(edges + edges_row_itr) = malloc(2 * (sizeof(int)));

for (int edges_column_itr = 0; edges_column_itr < 2; edges_column_itr++) {
char* edges_item_endptr;
char* edges_item_str = *(edges_item_temp + edges_column_itr);
int edges_item = strtol(edges_item_str, &edges_item_endptr, 10);

if (edges_item_endptr == edges_item_str || *edges_item_endptr != '\0') { exit(EXIT_FAILURE); }

*(*(edges + edges_row_itr) + edges_column_itr) = edges_item;
}
}

int result = farVertices(n, k, edges);

fprintf(fptr, "%d\n", result);

fclose(fptr);

return 0;
}

size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);

while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);

if (!line) { break; }

data_length += strlen(cursor);

if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

size_t new_length = alloc_length << 1;
data = realloc(data, new_length);

if (!data) { break; }

alloc_length = new_length;
}

if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}

char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");

int spaces = 0;

while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}

splits[spaces - 1] = token;

token = strtok(NULL, " ");
}

return splits;
}
```

{"mode":"full","isActive":false}