Cerinta completa
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 nodes (labeled to ) where a specific given node 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 and 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 ) 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 , denoting the number of test cases. testcases follow.
First line of each test case has two integers , denoting the number of cities in the map and , denoting the number of roads in the map.
The next lines each consist of two space-separated integers and denoting a main road between city and city .
The last line has an integer , denoting the current position of Rust.
Constraints
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
2
Sample Output 0
3 1 2
2 2 1
Explanation 0
The graph in the first testcase can be shown as:
Here the source 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
Limbajul de programare folosit: java8
Cod:
//Problem: https://www.hackerrank.com/challenges/rust-murderer
//Java 8
/*
Initial Thoughts: Since we know the graph of main roads, but need
to travel only on side roads, we will need to
get the inverse of the main road graph. Then we
can just run a bfs shortest path on the new graph
Optimization: Instead of inversing the graph, we can just run BFS on
all non-neighbors thus removing the inverse graph step
Per test case
Time Complexity: O(N + M) //We must visit every node once and we do so my way of the main roads
Space Complexity: O(N)
*/
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;
}
}
Scor obtinut: 1.0
Submission ID: 464604440
Link challenge: https://www.hackerrank.com/challenges/rust-murderer/problem