In this post, we will solve HackerRank Rust & Murderer Problem Solution.
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.
Input Format
The first line contains T, denoting the number of test cases. T testcases follow. First line of each test case has two integers N. denoting the number of cities in the map and M. denoting the number of roads in the map.
The next M lines each consist of two space-separated integers x and y denoting a main road between city a and city y. The last line has an integer S, denoting the current position of Rust.
Note
- No nodes will have a road to itself.
- There will not be multiple edges between any pair of nodes i.e. there is at most one undirected edge between them.
- Graph is guaranteed to be sparse.
- It is guranteed that there will be a path between any pair of nodes using the side lanes.
Output Format
For each of T test cases, print a single line consisting of N-1 space separated integers, denoting the shortest distances of the remaining N-1 places from Rust’s position (that is all distances, except the source node to itself) using the village roads/side lanes in ascending order based on vertex number.
Sample Input 0
2
4 3
1 2
2 3
1 4
1
4 2
1 2
2 3
2Sample Output 0
3 1 2
2 2 1Explanation 0
The graph in the first testcase can be shown as:
node is 1 (marked S).
The distance from 1 to 2 is 3. Path: 1 -> 3 -> 4 -> 2
The distance from 1 to 3 is 1. Path: 1 -> 3
The distance from 1 to 4 is 2. Path: 1 -> 3 -> 4
Rust & Murderer C Solution
#include <stdio.h>
#include <malloc.h>
#define MAX_NODES (15*10000)
#define MAX_ROAD (1000000)
#define PRINTF(s...)
//printf(s)
typedef struct t_road {
struct t_road *p_start_next;
struct t_road *p_end_next;
unsigned short start;
unsigned short end;
}ROAD, *pROAD;
typedef struct t_node {
pROAD p_road;
unsigned long distance;
unsigned long id:30;
unsigned long in_working_set:1;
unsigned long done:1;
}NODE;
typedef struct t_working_node {
unsigned long node:31;
unsigned long valid:1;
}WORKING_NODE;
typedef struct t_working_set {
unsigned long max_valid_index;
unsigned long valid_count;
WORKING_NODE working_nodes[MAX_NODES + 1];
}WORKING_SET;
NODE city_nodes[MAX_NODES + 1];
WORKING_SET working_set;
void add_to_working_set(NODE *pnodes, WORKING_SET *parrs, unsigned long curr_node, unsigned long dist)
{
unsigned long index;
PRINTF("[%s %i] node:%lu in_working_set:%i distance:%lu(%lu) count:%lu(%lu)\n",
__FUNCTION__, __LINE__, curr_node, pnodes[curr_node].in_working_set, pnodes[curr_node].distance, dist, parrs->valid_count, parrs->max_valid_index);
if(pnodes[curr_node].in_working_set) {
if(pnodes[curr_node].distance > dist)
pnodes[curr_node].distance = dist;
} else {
parrs->working_nodes[parrs->valid_count].node = curr_node;
parrs->valid_count++;
pnodes[curr_node].distance = dist;
pnodes[curr_node].in_working_set = 1;
}
}
unsigned long remove_smallest_from_working_set(NODE *pnodes, WORKING_SET *parrs)
{
unsigned long min_node;
if(parrs->valid_count == parrs->max_valid_index)
return 0;
min_node = parrs->working_nodes[parrs->max_valid_index].node;
parrs->max_valid_index++;
pnodes[min_node].done = 1;
PRINTF("[%s %i] node:%lu count:%lu(%lu)\n",
__FUNCTION__, __LINE__, min_node, parrs->valid_count, parrs->max_valid_index);
return min_node;
}
int
main(int argc, char *argv[])
{
unsigned long test_cases;
unsigned long cities, roads;
pROAD p_roads = NULL, p_temp_road;
unsigned long alloced_roads = 0;
unsigned long count, index, start, end, curr_id, start_location, write_index, index_1;
unsigned long city_node_index[MAX_NODES], city_node_count;
scanf("%lu", &test_cases);
for(count = 0; count < test_cases; count++) {
scanf("%lu %lu", &cities, &roads);
if(alloced_roads >= roads) {
} else {
if(p_roads)
free(p_roads);
p_roads = malloc(sizeof(ROAD) * roads);
alloced_roads = roads;
}
memset(&city_nodes, 0x00, (cities + 1) * sizeof(NODE));
memset(&working_set.working_nodes[0], 0x00, (cities + 1)*sizeof(WORKING_NODE));
working_set.max_valid_index = 0;
working_set.valid_count = 0;
for(index = 0; index < roads; index++) {
scanf("%lu %lu", &start, &end);
p_roads[index].start = start;
p_roads[index].end = end;
p_roads[index].p_start_next = city_nodes[start].p_road;
city_nodes[start].p_road = &p_roads[index];
city_nodes[start].distance = 0xffffffff;
p_roads[index].p_end_next = city_nodes[end].p_road;
city_nodes[end].p_road = &p_roads[index];
city_nodes[end].distance = 0xffffffff;
}
for(index = 0; index < cities; index++) {
city_node_index[index] = index + 1;
}
city_node_count = cities;
scanf("%lu", &start_location);
start = start_location;
end /* curr_value*/ = 0;
add_to_working_set(city_nodes, &working_set, start, end);
curr_id = 5; //any number
while((start = remove_smallest_from_working_set(city_nodes, &working_set)) > 0) {
/* from this node check where all we can reach (i.e. !via roads) */
curr_id++;
city_nodes[start].id = curr_id;
city_nodes[start].done = 1;
p_temp_road = city_nodes[start].p_road;
while(p_temp_road) {
if(p_temp_road->start == start) {
city_nodes[p_temp_road->end].id = curr_id;
p_temp_road = p_temp_road->p_start_next;
} else {
//printf("should not be coming here \n");
city_nodes[p_temp_road->start].id = curr_id;
p_temp_road = p_temp_road->p_end_next;
}
}
write_index = 0;
for(index = 0; index < city_node_count; index++) {
index_1 = city_node_index[index];
if(city_nodes[index_1].in_working_set == 1)
continue;
if(city_nodes[index_1].done)
continue;
city_node_index[write_index] = index_1;
write_index++;
if(city_nodes[index_1].id == curr_id)
continue;
add_to_working_set(city_nodes, &working_set, index_1, city_nodes[start].distance+1);
}
city_node_count = write_index;
}
for(index = 1; index <= cities; index++) {
if(index == start_location)
continue;
printf("%lu ", city_nodes[index].distance);
}
printf("\n");
}
}Rust & Murderer C++ Solution
#include <unordered_set>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 999999999
using namespace std;
struct node : unordered_set<int>
{
int dist;
node():dist(INF){}
};
int main()
{
int T;
cin>>T;
for(int t=0; t<T; t++)
{
unordered_set<int> tovisit;
int N, M;
cin>>N>>M;
for(int i=1; i<=N; i++) tovisit.insert(i);
node nodes[N+1];
for(int i=0, a, b; i<M; i++)
{
cin>>a>>b;
nodes[a].insert(b);
nodes[b].insert(a);
}
queue<int> Q;
int S;
cin>>S;
Q.push(S);
nodes[S].dist = 0;
tovisit.erase(S);
while(!tovisit.empty())
{
int act = Q.front();
Q.pop();
vector<int> torem;
for(auto a : tovisit)
if(nodes[act].find(a) == nodes[act].end())
if(nodes[a].dist == INF)
{
nodes[a].dist = nodes[act].dist + 1;
Q.push(a);
torem.push_back(a);
}
for(int i=0; i<torem.size(); i++)
tovisit.erase(torem[i]);
}
for(int i=1; i<=N; i++)
if(i != S)
cout<<nodes[i].dist<<" ";
cout<<"\n";
}
return 0;
}Rust & Murderer C Sharp Solution
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Xml.Serialization.Configuration;
namespace HackerRanking
{
[DebuggerDisplay("{Begin},{End} ({Weight})")]
class Node : IComparable<Node>
{
public Node(params int[] wInts)
{
Begin = wInts[0];
End = wInts[1];
if(wInts.Length > 2)
Weight = wInts[2];
}
public Node AddPath(BigInteger weight)
{
var node = new Node(Begin, End, Weight);
return node;
}
public int Begin;
public int End;
public int Weight;
public int CompareTo(Node other)
{
return -Weight.CompareTo(other.Weight);
}
public static Dictionary<int, List<Node>> constructGraph(int edgeCount, TextReader reader)
{
var graph = new Dictionary<int, List<Node>>(4 + edgeCount / 4);
for (int i = 0; i < edgeCount; i++)
{
var tuple = reader.ReadLine().Trim().Split(' ')
.Select(int.Parse)
.ToArray();
if (!graph.ContainsKey(tuple[0]))
graph[tuple[0]] = new List<Node>();
graph[tuple[0]].Add(new Node(tuple));
if (!graph.ContainsKey(tuple[1]))
graph[tuple[1]] = new List<Node>();
graph[tuple[1]].Add(new Node(new int[] { tuple[1], tuple[0] }));
}
return graph;
}
}
internal class SolutionRustAndMurderer
{
private static void Main(String[] args)
{
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
TextReader reader = null;
try
{
reader = File.OpenText(@"c:\temp\input06-RustAndMurderer.txt");
reader = new StringReader(@"2
4 3
1 2
2 3
1 4
1
4 2
1 2
2 3
2");
}
catch
{
reader = Console.In;
}
if (reader == null)
return;
var q = int.Parse(reader.ReadLine());
for (int i = 0; i < q; i++)
{
var tuple = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();
var nodesCount = tuple[0];
var edgeCount = tuple[1];
var graph = Node.constructGraph(edgeCount, reader);
var start = int.Parse(reader.ReadLine());
var s = doCount(start, nodesCount, graph);
//File.AppendAllText(@"c:\temp\o6.txt", s + '\n');
Console.WriteLine(s);
}
}
static string doCount(int start, int nodesCount, Dictionary<int, List<Node>> graph)
{
var res = new int[nodesCount+1];
var seen = new Dictionary<int, bool>();
if (!graph.ContainsKey(start))
{
return string.Join(" ", Enumerable.Range(1, nodesCount - 1)
.Select(j => 1));
}
var root = graph[start];
var queue = new Queue<int>();
var rootset = root.Select(nn => nn.End).ToDictionary(nn => nn, nn => true);
var complement = new SortedSet<int>();
var dist = 1;
for (int i = 1; i <= nodesCount; i++)
{
if (i == start || rootset.ContainsKey(i))
{
complement.Add(i);
continue;
}
res[i] = dist;
queue.Enqueue(i);
}
while (queue.Count > 0)
{
var n = queue.Dequeue();
if (n < 0)
{
dist = -n;
continue;
}
List<Node> node = (graph.ContainsKey(n)) ? graph[n] : new List<Node>() {new Node(0, 0, 0)};
queue.Enqueue(-dist - 1);
var tmpqueue = new Queue<int>();
foreach (var i in complement)
//for (int i = 1; i <= nodesCount; i++)
{
if (i == start || res[i] > 0)
continue;
if(node.Select(nn => nn.End).Any(e => e == i))
continue;
res[i] = dist + 1;
tmpqueue.Enqueue(i);
}
while (tmpqueue.Count > 0)
{
var i = tmpqueue.Dequeue();
queue.Enqueue(i);
complement.Remove(i);
}
}
var sb = new StringBuilder();
for (int i = 1; i < res.Length; i++)
{
if(i == start)
continue;
sb.Append(res[i]).Append(" ");
}
return sb.ToString();
}
}
}
Rust & Murderer Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
for(int t = 0; t < T; t++)
{
int N = input.nextInt();//Cities(nodes)
int M = input.nextInt();//Main roads(edges)
HashMap<Integer,HashSet<Integer>> cityMap = new HashMap<>();
//Build city map of main roads
for(int i = 0; i < M; i++)
{
int source = input.nextInt();
int target = input.nextInt();
if(cityMap.containsKey(source)) cityMap.get(source).add(target);
else
{
HashSet<Integer> roads = new HashSet<>(); roads.add(target);
cityMap.put(source, roads);
}
if(cityMap.containsKey(target)) cityMap.get(target).add(source);
else
{
HashSet<Integer> roads = new HashSet<>(); roads.add(source);
cityMap.put(target, roads);
}
}
//Starting point of search
int startingPoint = input.nextInt();
//Perform a BFS by traversing non-edges
int[] distances = BFS_Distance(startingPoint, cityMap, N);
//Print output
StringBuilder output = new StringBuilder("");
for(int i = 0; i < distances.length; i++)
{
if(i+1 != startingPoint)
output.append(distances[i]+" ");
}
System.out.println(output);
}
}
//Performs a BFS from starting point to all non-neighbors
static int[] BFS_Distance(int root, HashMap<Integer,HashSet<Integer>> graph, int N)
{
int[] distances = new int[N];
HashSet<Integer> notVisited = new HashSet<>();
HashSet<Integer> visited = new HashSet<>();
for(int i = 1; i <= N; i++) notVisited.add(i);
Queue<Integer> queue = new LinkedList<>();
queue.offer(root);
notVisited.remove(root);
distances[0] = 0;
while(!queue.isEmpty())
{
int curr = queue.poll();
HashSet<Integer> neighbors = graph.get(curr);
for(int nv : notVisited)
{
if(neighbors == null || !neighbors.contains(nv))
{
queue.offer(nv);
distances[nv-1] = distances[curr-1]+1;
visited.add(nv);
}
}
notVisited.removeAll(visited);
visited = new HashSet<>();
}
return distances;
}
}Rust & Murderer JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the rustMurdered function below.
*/
function rustMurderer(n, graph, s) {
const d = Array(n + 1);
const sv = new Set();
for (let i = 1; i <= n; i++) {
d[i] = Number.MAX_SAFE_INTEGER;
sv.add(i);
}
const stack = [];
stack.size = 0;
push(stack, s);
d[s] = 0;
sv.delete(s);
while (stack.size > 0) {
const v = pop(stack);
const edges = graph[v];
for (let i of sv) {
if (!edges[i] && d[i] > d[v]) {
d[i] = d[v] + 1;
push(stack, i);
sv.delete(i);
}
}
}
return d.filter((v, i) => !(i === 0 || i === s));
}
function pop(stack) {
return stack[--stack.size];
}
function push(stack, value) {
stack[stack.size++] = value;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const nm = readLine().split(' ');
const n = parseInt(nm[0], 10);
const m = parseInt(nm[1], 10);
let graph = Array(n + 1);
for (let i = 1; i <= n; i++) {
graph[i] = {};
}
for (let roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
const edge = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
graph[edge[0]][edge[1]] = true;
graph[edge[1]][edge[0]] = true;
}
const s = parseInt(readLine(), 10);
let result = rustMurderer(n, graph, s);
ws.write(result.join(" ") + "\n");
}
ws.end();
}Rust & Murderer Python Solution
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))
