HackerRank Rust & Murderer problem solution

In this HackerRank Rust & Murderer problem, Detective Rust is investigating a homicide and he wants to chase down the murderer. The murderer knows he would definitely get caught if he takes the main roads for fleeing, so he uses the village roads (or side lanes) for running away from the crime scene.

Rust knows that the murderer will take village roads and he wants to chase him down. He is observing the city map, but it doesn’t show the village roads (or side lanes) on it and shows only the main roads.

The map of the city is a graph consisting N nodes (labeled 1 to N) where a specific given node S represents the current position of Rust and the rest of the nodes denote other places in the city, and an edge between two nodes is a main road between two places in the city. It can be suitably assumed that an edge that doesn’t exist/isn’t shown on the map is a village road (side lane). That means, there is a village road between two nodes a and b iff(if and only if) there is no city road between them.

In this problem, distance is calculated as number of village roads (side lanes) between any two places in the city.

Rust wants to calculate the shortest distance from his position (Node S) to all the other places in the city if he travels only using the village roads (side lanes).

Note: The graph/map of the city is ensured to be a sparse graph.

HackerRank Rust & Murderer problem solution in Python.

tests = int(input())

for _ in range(tests):
    [n, e] = [int(i) for i in input().split(" ")]
    dists = [1] * n
    roads = {}
    for _ in range(e):
        [n1, n2] = [int(i) for i in input().split(" ")]
        if n1 not in roads:
            roads[n1] = set()
        if n2 not in roads:
            roads[n2] = set()
        roads[n1].add(n2)
        roads[n2].add(n1)
    start_loc = int(input())
    not_visited = roads[start_loc] if start_loc in roads else set()
    newly_visited = set()
    curr_dist = 2
    while len(not_visited) > 0:
        for i in not_visited:
            diff = not_visited | roads[i]
            if len(diff) < n:
                dists[i-1] = curr_dist
                newly_visited.add(i)
        not_visited = not_visited - newly_visited
        newly_visited = set()
        curr_dist += 1
    del dists[start_loc-1]
    print(" ".join(str(i) for i in dists))

Rust & Murderer problem solution in Java.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringJoiner;

public class Solution {

    public static void main(String [] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder resultBuilder = new StringBuilder();
        int numberOfTestCases = Integer.parseInt(bufferedReader.readLine());
        for(int t=0;t<numberOfTestCases;t++) {

            String [] parts = bufferedReader.readLine().split(" ");
            int numberOfNodes = Integer.parseInt(parts[0]);
            int numberOfMainRoads = Integer.parseInt(parts[1]);

            HashSet<Integer>[] mainRoadConnections = new HashSet[numberOfNodes + 1];
            for(int i=0;i<numberOfNodes + 1;i++) {
                mainRoadConnections[i] = new HashSet();
            }

            for(int i=0;i<numberOfMainRoads;i++) {
                parts = bufferedReader.readLine().split(" ");
                int from = Integer.parseInt(parts[0]);
                int to = Integer.parseInt(parts[1]);

                mainRoadConnections[from].add(to);
                mainRoadConnections[to].add(from);
            }

            int start = Integer.parseInt(bufferedReader.readLine());

            int [] distances = solve(numberOfNodes, mainRoadConnections, start);

            StringJoiner stringJoiner = new StringJoiner(" ");
            for(int i=1;i<numberOfNodes + 1;i++) {
                if (i!=start) {
                    stringJoiner.add(distances[i] + "");
                }
            }

            resultBuilder.append(stringJoiner.toString() +"n");
        }

        System.out.println(resultBuilder.toString());
    }

    private static int[] solve(int numberOfNodes, HashSet<Integer>[] mainRoadConnections, int start) {

        boolean visited [] = new boolean[numberOfNodes + 1];
        int result [] = new int [numberOfNodes + 1];
        Arrays.fill(result, Integer.MAX_VALUE);

        LinkedList<Node> queue = new LinkedList<>();
        queue.add(new Node(start, 0));

        HashSet<Integer> notUsed = new HashSet<>();
        for(int i=1;i<=numberOfNodes;i++) {
            notUsed.add(i);
        }
        notUsed.remove(start);

        while(!queue.isEmpty()) {

            Node top = queue.poll();

            result[top.index] = top.distance;

            HashSet<Integer> forRemove = new HashSet<>();
            for(Integer i : notUsed) {
                if (i != top.index && !visited[i] && !mainRoadConnections[top.index].contains(i)) {
                    visited[i] = true;
                    forRemove.add(i);
                    queue.add(new Node(i, top.distance + 1));
                }
            }

            notUsed.removeAll(forRemove);
        }

        return result;
    }

    private static class Node {
        int index;
        int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }
    }
}

Problem solution in C++.

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;
int dp[150000+1];
vector<int> graph[150002];
set<int> S;
queue<int> Q;

int main()
{
    int t,nodes,edges,start;
    int v1,v2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&nodes,&edges);
        for(int i=1; i<= nodes; i++) graph[i].clear();
        for(int i=1; i<= edges; i++)
        {
            scanf("%d %d",&v1,&v2);
            graph[v1].push_back(v2);
            graph[v2].push_back(v1);
        }
        scanf("%d",&start);
        for(int i=1; i<=nodes; i++)
            S.insert(i);
        S.erase(start);
        dp[start] = 0;
        Q.push(start);
        while(!Q.empty())
        {
            int ele = Q.front();
            set<int> R;
            Q.pop();
            int sz = graph[ele].size();
            for(int i=0; i<sz; i++)
            {
                int x = graph[ele][i];
                if (S.find(x) != S.end())
                {
                    S.erase(x);
                    R.insert(x);
                }
            }
            set<int>::iterator itr;
            for(itr = S.begin(); itr != S.end(); itr++)
            {
                Q.push(*itr);
                dp[*itr] = dp[ele] + 1;
                S.erase(*itr);
            }
            S=R;
        }
        for(int i=1; i<=nodes; i++ )
        {
            if( i == start) continue;
            printf("%d ",dp[i]);
        }
        printf("n");
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
  int x;
  struct _node *next;
} node;
void add_edge(int x,int y);
void clean();
int N,M;
int ans[500000],d[500000],unsolve[2][500000],unsolve_size[2],temp[500000];
node *list[500000]={0};

int main(){
  int T,S,x,y,solve,r_idx,w_idx,c,temp_size,count,i;
  node *p;
  scanf("%d",&T);
  while(T--){
    solve=c=w_idx=1;
    r_idx=0;
    scanf("%d%d",&N,&M);
    for(i=0;i<N;i++){
      d[i]=0;
      ans[i]=-1;
    }
    for(i=0;i<M;i++){
      scanf("%d%d",&x,&y);
      add_edge(x-1,y-1);
      d[x-1]++;
      d[y-1]++;
    }
    scanf("%d",&S);
    ans[S-1]=0;
    unsolve_size[r_idx]=0;
    for(i=0;i<N;i++)
      if(ans[i]==-1)
        unsolve[r_idx][unsolve_size[r_idx]++]=i;
    while(unsolve_size[r_idx]){
      temp_size=0;
      unsolve_size[w_idx]=0;
      for(i=0;i<unsolve_size[r_idx];i++)
        if(d[unsolve[r_idx][i]]<solve)
          temp[temp_size++]=unsolve[r_idx][i];
        else{
          for(count=0,p=list[unsolve[r_idx][i]];p;p=p->next)
            if(ans[p->x]!=-1)
              count++;
          if(count<solve)
            temp[temp_size++]=unsolve[r_idx][i];
          else
            unsolve[w_idx][unsolve_size[w_idx]++]=unsolve[r_idx][i];
        }
      for(i=0;i<temp_size;i++)
        ans[temp[i]]=c;
      solve+=temp_size;
      c++;
      r_idx=(r_idx+1)%2;
      w_idx=(w_idx+1)%2;
    }
    for(i=0;i<N;i++)
      if(i!=S-1)
        printf("%d ",ans[i]);
    printf("n");
    clean();
  }
  return 0;
}
void add_edge(int x,int y){
  node *p1,*p2;
  p1=(node*)malloc(sizeof(node));
  p2=(node*)malloc(sizeof(node));
  p1->x=x;
  p1->next=list[y];
  list[y]=p1;
  p2->x=y;
  p2->next=list[x];
  list[x]=p2;
  return;
}
void clean(){
  int i;
  node *p1,*p2;
  for(i=0;i<N;i++)
    if(list[i]){
      p1=list[i];
      while(p1){
        p2=p1;
        p1=p1->next;
        free(p2);
      }
      list[i]=NULL;
    }
  return;
}