HackerRank Repair Roads Problem Solution

HackerRank Repair Roads Problem Solution

Yashwant Parihar,

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  
2

Explanation
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.

HackerRank Repair Roads Problem Solution
HackerRank Repair Roads Problem Solution

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()
c C# C++ HackerRank Solutions java javascript python