We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Graph Theory
- Rust & Murderer
- Discussions
Rust & Murderer
Rust & Murderer
+ 0 comments Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Rust & Murderer Problem Solution
+ 0 comments Here is the solution of Rust & Murderer Click here
+ 1 comment vector<int> rustMurderer(int n, vector<vector<int>> roads, int s) { /* * Write your code here. */ unordered_map<int, unordered_set<int>> graph; /* Represent an input as a graph based on unordered_... types for the maximum insertion/removal performance. */ for (int i = 1; i <= n; ++i) graph[i] = unordered_set<int>{}; for (const auto& edge : roads) { graph[edge[0]].insert(edge[1]); graph[edge[1]].insert(edge[0]); } /* A list (set) of the top nodes. A top node is a node that we are currently analyse paths from. The top nodes have always the minimum possible distance measured as required by the task. */ unordered_set<int> tops; /* The resulting distances. This vector also includes an element for a node `s` which will be removed later. */ vector<int> distances(n); int current_distance = 0; /* Kickstart the process from the given node */ tops.insert(s); distances[s - 1] = current_distance++; while (!tops.empty()) { unordered_map<int, int> ntops_paths; /* On each iteration we remove nodes and edges of the graph that are already processed, thus each node and edge is effectively visited once. */ /* Now find out how many direct (one step) paths are there from the current list of top nodes to all nodes of the remaining graph. */ /* Start with listing all possible nodes. */ for (const auto& kvp : graph) ntops_paths[kvp.first] = 0; /* As soon as the direct path found, increment the number of paths to the node. */ for (const auto from : tops) { for (const auto to : graph[from]) { ntops_paths[to]++; graph[to].erase(from); /* Erase backward edge. */ } ntops_paths.erase(from); /* Exclude top nodes from further analysis. */ graph.erase(from); /* Erase the visited node with all forward edges. */ } /* Now construct a new list of top nodes based on the fact that each node that is unreachable from at least one of the current top nodes via a "main road" is reachable via "side road". Effectively it means that the path number calculated above is at least 1 less than the number of the current top nodes. */ unordered_set<int> ntops; for (const auto& kvp : ntops_paths) if (kvp.second < tops.size()) ntops.insert(kvp.first); /* Populate distances for the new top nodes. */ for (const auto top : ntops) distances[top - 1] = current_distance; ++current_distance; /* Replace the current list of top nodes with the new one. */ tops = move(ntops); } distances.erase(distances.begin() + s - 1); return distances; }
+ 0 comments If someone is having runtime error in test cases 1, 2, 4 and 5, take into account that the "s" node may not have main road connections.
+ 1 comment It is Dijkstra's algorithm with a twist. Be sure to keep track of already connected (side path found from s) nodes and exclude them from the loop.
Load more conversations
Sort 66 Discussions, By:
Please Login in order to post a comment