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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Rust & Murderer
  5. Discussions

Rust & Murderer

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 64 Discussions, By:

recency

Please Login in order to post a comment

  • nkozlov
    6 months ago+ 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|
    Permalink
  • adegregorio
    2 years ago+ 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|
    Permalink
  • Kairn
    2 years ago+ 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|
    Permalink
  • IT_1834813023
    2 years ago+ 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|
    Permalink
  • joe44850
    2 years ago+ 0 comments

    I've read the description for this about 28 times and still can't figure out what they are asking for.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy