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
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))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;
}
0 Comments