# HackerRank Rust & Murderer problem solution

In this HackerRank Rust & Murderer problem, distance is calculated as several 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).

## Problem solution in Python.

```tests = int(input())

for _ in range(tests):
[n, e] = [int(i) for i in input().split(" ")]
dists = [1] * n
for _ in range(e):
[n1, n2] = [int(i) for i in input().split(" ")]
start_loc = int(input())
newly_visited = set()
curr_dist = 2
while len(not_visited) > 0:
for i in not_visited:
if len(diff) < n:
dists[i-1] = curr_dist
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))```

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

## Problem solution in Java.

```import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringJoiner;

public class Solution {

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

StringBuilder resultBuilder = new StringBuilder();
for(int t=0;t<numberOfTestCases;t++) {

int numberOfNodes = Integer.parseInt(parts[0]);

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

int from = Integer.parseInt(parts[0]);
int to = Integer.parseInt(parts[1]);

}

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

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

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

HashSet<Integer> notUsed = new HashSet<>();
for(int i=1;i<=numberOfNodes;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;
}
}

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;
}
}
}
```

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

## 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;
}
```

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

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int x;
struct _node *next;
} node;
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);
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;
}
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;
}
```

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