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 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.
+ 0 comments 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.
+ 0 comments Wrote this code and got a tle on test case 6 only. Help any one ??
void solve(){ ll n,e; cin>>n>>e; unordered_map<ll,list<ll>> m; vector<ll> dis(n+1,INT_MAX); queue<ll> q; set<ll> l; for(ll i=0;i<n;i++){ l.insert(i+1); } for(ll i=0;i<e;i++){ ll a,b; cin>>a>>b; m[a].push_back(b); m[b].push_back(a); } ll start; cin>>start; q.push(start); l.erase(start); dis[start]=0; while(!q.empty() and l.size()){ ll p=q.front(); q.pop(); list<ll> ne; for(ll x:l){ if(find(m[p].begin(),m[p].end(),x)==m[p].end()){ ne.push_back(x); } } for(ll x:ne){ q.push(x); dis[x]=dis[p]+1; l.erase(x); } } for(auto a:dis){ if(a==0 or a==INT_MAX) continue; cout<<a<<" "; } cout<<endl; }
+ 0 comments I've read the description for this about 28 times and still can't figure out what they are asking for.
Load more conversations
Sort 64 Discussions, By:
Please Login in order to post a comment