# HackerRank Repair Roads problem solution

In this HackerRank Repair Roads problem solution Two roads are adjacent if they have the same city at one of their endpoints. For the process to be efficient, no two robots will ever repair the same road, and no road can be visited twice. What is the minimum number of robots needed to accomplish the task?

## Problem solution in Python.

```#!/bin/python3

import os
import sys

#
# Complete the repairRoads function below.
#
import collections
import queue

def solve():
n = int(input().strip())

graph = dict((i, []) for i in range(0, n))

for j in range(n - 1):
x, y = [int(p) for p in input().strip().split()]
graph[x].append(y)
graph[y].append(x)

# transform graph into tree
level = 1

root = 0
q = queue.Queue()
q.put((root, level, None))
seen = set([])

levels = collections.defaultdict(set)
tree = {}

while not q.empty():
item, level, parent = q.get()

tree[item] = dict(id=item, parent=parent, level=level, children=set([]),
leaf=None)

for child in graph[item]:
if child not in seen:
q.put((child, level + 1, item))

# print('Levels: %s' % levels)
# print('Tree: %s' % tree)

# count clusters
clusters = 1
has_items_in_cluster = False

for level in sorted(levels.keys(), reverse=True):
for item in levels[level]:
tree_item = tree[item]
if not tree_item['children']:  # leaf
tree_item['leaf'] = True
else:
has_items_in_cluster = True

branches = 0
for child in tree_item['children']:
if not tree[child]['leaf']:
branches += 1

# branches == 0 -> visit point and go up
# branches == 1 -> visit downstream, point and go up
# branches % 2 == 0 -> have (branches // 2) clusters
# branches % 2 == 1 -> have  (branches // 2) clusters and go up
if branches >= 2:
new_clusters = branches // 2

clusters += new_clusters
# print('New clusters: %d' % new_clusters)

if branches % 2 == 0:
has_items_in_cluster = False
# cluster will also include road up
parent = tree_item['parent']
if parent is not None:
# print('Cut %s and %s' % (item, parent))
tree[parent]['children'].remove(item)

# print(tree[item])

# print('Tree: %s' % tree)

if not has_items_in_cluster:
clusters -= 1  # last cluster was created but has no items

print(clusters)

t = int(input().strip())

for tt in range(t):
solve()
```

{"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 {

private Map<Integer, List<Integer>> roads = new HashMap<>();
/*
* Complete the repairRoads function below.
*/
/*
*/

Solution solution = new Solution();
for(int i=0;i<n-1;i++)
{
}
return solution.solve();
}

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")));

int t = Integer.parseInt(scanner.nextLine().trim());

for (int tItr = 0; tItr < t; tItr++) {
int n = Integer.parseInt(scanner.nextLine().trim());

}
}

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

bufferedWriter.close();
}

if (parent != null) {
}
for (Integer c : roadsFromCity) {
}
}

public int solve() {
int result = 0;
int level = 0;
for (int i = roadTree.levels.lastKey() - 1; i > 0; i--) {
for (Integer city : cities) {
if (leaves != null && leaves.isEmpty() == false) {
for (Integer integer : leaves) {
}
} else if (roadTree.points[city] % 2 == 0) {
}
for (Integer integer : leaves) {
}
}
}
}
}
return result + (roadTree.points[root] + 1) / 2;
}

private int[] parents;
private Map<Integer, List<Integer>> roads = new HashMap<>();
private TreeMap<Integer, List<Integer>> levels = new TreeMap<>();
private int[] points;

points = new int[numberOfCities];
parents = new int[numberOfCities];
}

if (levels.containsKey(level) == false) {
levels.put(level, new ArrayList<Integer>());
}
for (Integer integer : roads) {
parents[integer] = city;
}
}

public void remove(Integer city) {
}

}
}

private void addConnection(int city1, int city2) {
} else {
List<Integer> cities = new ArrayList<>();
}
}

}
```

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

## Problem solution in C++.

```#include<iostream>
#include<vector>
#include<stdio.h>
#include<set>
#include<string.h>
#include<stdlib.h>
using namespace std ;
#define INF (int)1e9
#define MAXN 10002
vector<int> G[MAXN] ;
int n ;

int parent[MAXN] ;
void dfs(int k,int p)
{
parent[k] = p ;
for(int i = 0;i < G[k].size();i++)
if(G[k][i] != p)
dfs(G[k][i],k) ;
}

int u[MAXN],v[MAXN],f[MAXN],nleaf[MAXN] ;
int solve()
{
memset(u,0,sizeof u) ;
memset(v,0,sizeof v) ;
memset(nleaf,0,sizeof nleaf) ;
memset(parent,255,sizeof parent) ;
dfs(0,-1) ;
for(int i = 1;i < n;i++) nleaf[parent[i]]++ ;
int nodes = n,ret = 0 ;
for(int i = 1;i < n;i++) if(nleaf[i] == 0 && u[i] == 0)
{
nleaf[parent[i]]-- ;
u[parent[i]] = 1 ;
parent[i] = -1 ;
nodes-- ;
}
if(nodes == 1) return 1 ;

while(nodes > 1)
{
ret++ ;
memset(f,255,sizeof f) ;
char mark[MAXN] = {} ;
for(int i = 1;i < n;i++) if(parent[i] != -1)
if(nleaf[i] > 1)
mark[i] = 1 ;
int a = -1,b = -1,c = -1 ;
for(int i = 1;i < n;i++) if(parent[i] != -1) if(nleaf[i] == 0)
{
int j = i ;
while(j > 0 && !mark[j]) j = parent[j] ;
if(f[j] == -1) f[j] = i ;
else
{
a = f[j] ;
b = i ;
c = j ;
break ;
}
}
if(a == -1 || b == -1) break ;
while(a != c) { int t = parent[a] ; parent[a] = -1 ; nleaf[t]-- ; nodes-- ; a = t ; }
while(b != c) { int t = parent[b] ; parent[b] = -1 ; nleaf[t]-- ; nodes-- ; b = t ; }
u[c] = 0 ;
for(int i = 1;i < n;i++) if(parent[i] == c) v[i] = 1 ;
v[c] = 1 ;
if(nodes == 1) break ;

if(c > 0 && nleaf[c] == 0) { int t = parent[c] ; parent[c] = -1 ; nleaf[t]-- ; nodes-- ; c = t ; }
while(c > 0 && nleaf[c] == 0 && !u[c])
{
if(v[c]) { int t = parent[c] ; parent[c] = -1 ; nleaf[t]-- ; nodes-- ; c = t ; }
else { int t = parent[c] ; parent[c] = -1 ; u[t] = 1 ; nleaf[t]-- ; nodes-- ; c = t ; }
}
if(nodes == 1 && c == 0 && u[c]) ret++ ;
}
return ret ;
}

int main()
{
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
scanf("%d",&n) ;
for(int i = 0;i < MAXN;i++) G[i].clear() ;
for(int i = 1;i < n;i++)
{
int a,b ;
scanf("%d%d",&a,&b) ;
G[a].push_back(b) ;
G[b].push_back(a) ;
}
int ret = solve() ;
printf("%d\n",ret) ;
}
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>

char** split_string(char*);

struct edge{
int from;
int to;
};

bool precedge(struct edge e1, struct edge e2){
return e1.from < e2.from || (e1.from == e2.from && e1.to < e2.to);
}

void setuptree(int n, int** edges, struct edge *sortedge, int* edgebds, int* parentlist, int** childrenlist, int* numchildren, int* parentqueue){
for(int i = 0; i < n - 1; i++){
sortedge[2*i].from = edges[i][0];
sortedge[2*i].to = edges[i][1];
sortedge[2*i + 1].from = edges[i][1];
sortedge[2*i + 1].to = edges[i][0];
}

for(int i = 0; i < 2*(n - 1); i++){
int curr = i;
while(curr > 0){
int next = (curr - 1)/2;
if(precedge(sortedge[next], sortedge[curr])){
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 && precedge(sortedge[next], sortedge[2*curr + 1])){
next = 2*curr + 1;
}
if(2*curr + 2 < i && precedge(sortedge[next], sortedge[2*curr + 2])){
next = 2*curr + 2;
}
if(next != curr){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}

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

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

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

while(queuedone < queuesize){
int currnode = parentqueue[queuedone];
for(int i = edgebds[currnode]; i < edgebds[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++;
}
}

struct edge sortedge[2*(n - 1)];
int edgebds[n + 1], parentlist[n], *childrenlist[n], numchildren[n], parentqueue[n];
setuptree(n, roads, sortedge, edgebds, parentlist, childrenlist, numchildren, parentqueue);

int introb[n];//Number of robots to cover all roads below i
int extrob[n];//Number of robots to cover all roads below i plus ith parent road
int freerob[n];//Number of robots to cover all roads below i with one free to go to parent
int bypass[n];//Number of robots to cover all roads below i and not connected
for(int i = n - 1; i >= 0; i--){
int currnode = parentqueue[i];
introb[currnode] = 0;
extrob[currnode] = 1;
freerob[currnode] = 1;
bypass[currnode] = 0;
for(int j = 0; j < numchildren[currnode]; j++){
int childnode = childrenlist[currnode][j];
int oldint = introb[currnode];
int oldext = extrob[currnode];
int oldfree = freerob[currnode];
int oldby = bypass[currnode];

int check1, check2, check3;

check1 = oldint + extrob[childnode];
check2 = oldext + introb[childnode];
check3 = oldfree + freerob[childnode] - 1;
introb[currnode] = (check1 < check2? (check1 < check3? check1 : check3) : (check2 < check3? check2 : check3));

check1 = oldint + freerob[childnode];
check2 = oldext + introb[childnode];
check3 = oldfree + freerob[childnode] - 1;
extrob[currnode] = (check1 < check2? (check1 < check3? check1 : check3) : (check2 < check3? check2 : check3));

check1 = oldby + freerob[childnode];
check2 = oldfree + introb[childnode];
freerob[currnode] = (check1 < check2? check1 : check2);

check1 = oldby + introb[childnode];
check2 = oldfree + freerob[childnode] - 1;
bypass[currnode] = (check1 < check2? check1 : check2);
}
}

for(int i = 0; i < n; i++){
printf("%d: %d %d %d %d\n", i, introb[i], extrob[i], freerob[i], bypass[i]);
}
printf("\n");
return introb[0];
}

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

char* t_endptr;
int t = strtol(t_str, &t_endptr, 10);

if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }

for (int t_itr = 0; t_itr < t; t_itr++) {
char* n_endptr;
int n = strtol(n_str, &n_endptr, 10);

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

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

}
}

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}