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.

vector<int>rustMurderer(intn,vector<vector<int>>roads,ints){/* * 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(inti=1;i<=n;++i)graph[i]=unordered_set<int>{};for(constauto&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);intcurrent_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(constauto&kvp:graph)ntops_paths[kvp.first]=0;/* As soon as the direct path found, increment the number of paths to the node. */for(constautofrom:tops){for(constautoto: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(constauto&kvp:ntops_paths)if(kvp.second<tops.size())ntops.insert(kvp.first);/* Populate distances for the new top nodes. */for(constautotop: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);returndistances;}

## Rust & Murderer

You are viewing a single comment's thread. Return to all comments →