In this post, we will solve HackerRank Repair Roads Problem Solution.
The country of Byteland contains N cities and N – 1 bidirectional roads. There is a path between any two cities. The roads in Byteland were built long ago, and now they are in need of repair. You have been hired to fix all the roads. You intend to do this by dispatching robots on some of the roads. Each robot will repair the road he is currently on and then moves to one of the adjacent unrepaired roads. After repairing that, it will move to another adjacent unrepaired road, repair that and so on.
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?
Input Format
The first line contains the number of test cases T. T test cases follow. The first line of each test case contains N. the number of cities in Byteland. The cities are numbered 0..N – 1. The following N – 1 lines contain the description of the roads. The ith line contains two integers ai and bi meaning that there is a road connecting cities with numbers ai and bi.
Output Format
Print T lines, one corresponding to each test case containing the required answer for that test case.
Sample Input
3
4
0 1
0 2
0 3
6
0 1
1 2
2 3
2 4
4 5
7
0 1
1 2
2 3
2 4
4 5
3 6
Sample Output
1
1
2Explanation
For the first case, one robot is enough to repair all roads: (0,1)(0, 2) (0,3) For the second case, one robot is again enough:
(0, 1)→ (1, 2)→ (2,3) (2, 4)→ (4,5)
The the third case, there is no way to repair all the roads with one robot and at least two
are needed.
Repair Roads C Solution
#include <stdio.h>
#define NMAX 10005
int HEAD[NMAX];
int ENEXT[NMAX * 2];
int EDEST[NMAX * 2];
static void load()
{
int i, N;
int nE = 0, e;
scanf("%d", &N);
for (i = 0; i < N; ++i)
HEAD[i] = 0;
for (i = 1; i < N; ++i) {
int a, b;
scanf("%d %d", &a, &b);
/*printf("add %d,%d\n", a, b);*/
e = ++nE;
ENEXT[e] = HEAD[a];
EDEST[e] = b;
HEAD[a] = e;
e = ++nE;
ENEXT[e] = HEAD[b];
EDEST[e] = a;
HEAD[b] = e;
}
}
enum {
COOL = 0,
NORMAL = 1,
LAME = 2
};
static int dfs(int u, int p, int *desc)
{
int n_cool = 0;
int n_lame = 0;
int sum = 0;
int e;
int V0, V1, V2;
/*printf("+dfs(%d, %d)\n", u, p);*/
for (e = HEAD[u]; e; e = ENEXT[e]) {
int v = EDEST[e];
if (v == p)
continue;
sum += dfs(v, u, desc);
if (*desc == COOL)
++n_cool;
if (*desc == LAME)
++n_lame;
}
/*printf(" dfs(%d, %d): n_cool=%d n_lame=%d sum=%d\n", u, p, n_cool, n_lame, sum);*/
if (n_cool & 1)
V0 = sum - n_cool / 2;
else
V0 = sum - n_cool / 2 + 1;
if (n_cool > 0)
V1 = sum - n_cool / 2;
else
V1 = sum + 1;
if (n_cool > 0)
V2 = sum - n_cool / 2;
else if (n_lame == 0)
V2 = sum;
else
V2 = sum + 1;
/*printf(" dfs(%d, %d): V0=%d V1=%d V2=%d\n", u, p, V0, V1, V2);*/
if (V0 == V1 && V1 == V2)
*desc = COOL;
else if (V0 == V1)
*desc = LAME;
else
*desc = NORMAL;
/*printf("-dfs(%d, %d) = (%d, %d)\n", u, p, V2, *desc);*/
return V2;
}
static int solve()
{
/*puts("-------");*/
int desc;
return dfs(0, -1, &desc);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
load();
printf("%d\n", solve());
}
return 0;
}Repair Roads C++ Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
void dfs(int *fl,int* v,vector<vector<int>>&gr,int *dp,int i)
{
v[i]=1;
int z=0,o=0,t=0,oo=0;
for(int j=0;j<gr[i].size();++j)
{
int d=gr[i][j];
if(v[d]==0)
{
dfs(fl,v,gr,dp,d);
dp[i]+=dp[d];
if(fl[d]==0 && dp[d]>0)
++z;
else if(fl[d]==1 && dp[d]>0)
++o;
else if(fl[d]==2 && dp[d]>0)
++t;
else if(dp[d]==0)
++oo;
}
}
if(dp[i]==0 && gr[i].size()>1)
{
dp[i]=1;
return;
}
if(z>0)
{
dp[i]-=z/2;
if(z%2==0)
fl[i]=1;
}
else if(t>0 || oo>0)
{
dp[i]++;
fl[i]=0;
}
else if(o>0)
fl[i]=2;
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;++i)
{
int n;
cin>>n;
if(n==1)
{
cout<<0<<endl;
continue;
}
else if(n==2)
{
cout<<1<<endl;
continue;
}
vector<vector<int>>gr(n+1);
for(int i=0;i<n-1;i++)
{
int u,v;
cin>>u>>v;
gr[u].pb(v);
gr[v].pb(u);
}
int dp[n+1]={0};
int v[n+1]={0};
int fl[n+1]={0};
dfs(fl,v,gr,dp,0);
cout<<dp[0]<<endl;
}
}Repair Roads C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
/*
* Complete the repairRoads function below.
*/
public class N5
{
public int n,rez;
public List<bool> bl = new List<bool>();
public List<int> list = new List<int>();
public int dist;
public int val;
public bool isV = false,one=false,two=false;
public N5(int nn) { n = nn; }
}
static Dictionary<int, N5> dict;
static int sub;
static int repairRoads(int n, int[][] roads) {
/*
* Write your code here.
*/
dict = new Dictionary<int, N5>();
int num = 0;
for (int i = 0; i < roads.Length; i++)
{
N5 val;
var r = roads[i];
dict.TryGetValue(r[0], out val);
if (val == null)
{
N5 nr = new N5(r[0]);
nr.list.Add(r[1]);
nr.bl.Add(false);
dict.Add(r[0], nr);
}
else
{
val.bl.Add(false);
val.list.Add(r[1]);
}
N5 val2;
dict.TryGetValue(r[1], out val2);
if (val2 == null)
{
N5 nr = new N5(r[1]);
nr.list.Add(r[0]);
nr.bl.Add(false);
dict.Add(r[1], nr);
}
else
{
val2.bl.Add(false);
val2.list.Add(r[0]);
}
}
int start = 0;
N5 st;
dict.TryGetValue(start, out st);
while (start < roads.Length)
{
dict.TryGetValue(start, out st);
if (st != null && st.list.Count ==1)
{
st.isV = true;
break;
}
start++;
}
dfsRoads(start, null);
if(st==null)
return 0;
if (st.dist == 2) st.val++;
return st.val/2+st.val%2;
}
public static void dfsRoads(int start, N5 prev)
{
N5 next;
dict.TryGetValue(start, out next);
List<N5> ll = new List<N5>();
// if (next.isV==false)
{
// if (next != null && next.list.Count >1)
{
for (int i = 0; i < next.list.Count; i++)
{
N5 pr;
dict.TryGetValue(next.list[i], out pr);
if (pr != null && pr.isV == false)
{
ll.Add(pr);
pr.isV = true;
dfsRoads(next.list[i], next);
}
}
int lmax = 0,lmin=int.MaxValue,sum=0,one=0,count=0,v=0;
for (int i = 0; i < ll.Count; i++) {
if (ll[i].dist > lmax) { lmax = ll[i].dist; }
if (ll[i].dist < lmin) { lmin = ll[i].dist; }
if(ll[i].dist>1)count++;
if(ll[i].dist==2&&ll[i].two==false){
v++;
}
sum+=ll[i].val;
/*
if (ll[i].dist == 1&&ll[i].one)
{
if (ll[i].val > 1) sum += ll[i].val;
one = 1;
}
else
{
v = ll[i].val;
count++;
sum += ll[i].val;
}
*/
}
if (lmax == 0)
{
if (ll.Count == 1 && ll[0].one == true)
{ next.two = true; }
next.dist = 1;
}
else
if (count > 1&&(sum+v)%2==0)
{
next.one = true;
sum += v;
next.dist = 0;
}
else
{
next.dist = lmax + 1;
if (count >= 1) sum += v;
}
next.val = sum;
/*
if (sum > 0)
next.val = sum;
else
next.val = 1;
if (count > 1)
next.dist = 1;
else
next.dist=lmax+1;
if (lmin > 0 &&sum>0&& one == 1) next.val++;
*/
}
/*
else
if (next != null&&next.list.Count == 1) {
next.dist=1;
next.val=1;
next.one = true;
}
*/
}
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int t = Convert.ToInt32(Console.ReadLine());
for (int tItr = 0; tItr < t; tItr++) {
int n = Convert.ToInt32(Console.ReadLine());
int[][] roads = new int[n-1][];
for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
roads[roadsRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), roadsTemp => Convert.ToInt32(roadsTemp));
}
int result = repairRoads(n, roads);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}Repair Roads Java Solution
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.
*/
static int repairRoads(int n, int[][] roads) {
/*
* Write your code here.
*/
Solution solution = new Solution();
for(int i=0;i<n-1;i++)
{
System.out.println(roads[i][0] + "-" + roads[i][1]);
solution.addRoad(roads[i][0],roads[i][1]);
}
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());
int[][] roads = new int[n-1][2];
for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
String[] roadsRowItems = scanner.nextLine().split(" ");
for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr].trim());
roads[roadsRowItr][roadsColumnItr] = roadsItem;
}
}
int result = repairRoads(n, roads);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
}
private void addToTree(RoadTree roadTree, int level, Integer city, Integer parent) {
List<Integer> roadsFromCity = roads.get(city);
if (parent != null) {
roadsFromCity.remove(parent);
}
roadTree.add(city, roadsFromCity, level + 1);
for (Integer c : roadsFromCity) {
addToTree(roadTree, level + 1, c, city);
}
}
public int solve() {
int result = 0;
int level = 0;
RoadTree roadTree = new RoadTree(roads.size());
Integer root = roads.keySet().iterator().next();
addToTree(roadTree, level, root, null);
for (int i = roadTree.levels.lastKey() - 1; i > 0; i--) {
List<Integer> cities = roadTree.levels.get(i);
for (Integer city : cities) {
List<Integer> leaves = roadTree.roads.get(city);
if (leaves != null && leaves.isEmpty() == false) {
for (Integer integer : leaves) {
roadTree.points[city] += roadTree.points[integer];
}
if (roadTree.points[city] == 0) {
roadTree.points[city]++;
} else if (roadTree.points[city] % 2 == 0) {
result += roadTree.points[city] / 2;
roadTree.points[city] = 0;
}
for (Integer integer : leaves) {
roadTree.roads.remove(integer);
}
if (roadTree.points[city] == 0) {
roadTree.remove(city);
}
}
}
}
return result + (roadTree.points[root] + 1) / 2;
}
public static class RoadTree {
private int[] parents;
private Map<Integer, List<Integer>> roads = new HashMap<>();
private TreeMap<Integer, List<Integer>> levels = new TreeMap<>();
private int[] points;
public RoadTree(int numberOfCities) {
points = new int[numberOfCities];
parents = new int[numberOfCities];
}
public void add(Integer city, List<Integer> roads, Integer level) {
if (levels.containsKey(level) == false) {
levels.put(level, new ArrayList<Integer>());
}
this.roads.put(city, roads);
levels.get(level).add(city);
for (Integer integer : roads) {
parents[integer] = city;
}
}
public void remove(Integer city) {
roads.get(parents[city]).remove(city);
roads.remove(city);
}
}
public void addRoad(int city1, int city2) {
addConnection(city1, city2);
addConnection(city2, city1);
}
private void addConnection(int city1, int city2) {
if (roads.containsKey(city1)) {
roads.get(city1).add(city2);
} else {
List<Integer> cities = new ArrayList<>();
cities.add(city2);
roads.put(city1, cities);
}
}
}
Repair Roads Python Solution
#!/bin/python3
import os
import sys
#
# Complete the repairRoads function below.
#
import collections
import queue
def solve():
n = int(input().strip())
# read graph
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()
levels[level].add(item)
seen.add(item)
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))
seen.add(child)
tree[item]['children'].add(child)
# 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()
