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.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Rust & Murderer
  5. Discussions

Rust & Murderer

Sort by

recency

|

69 Discussions

|

  • zoyashah41306
     + 0 comments

    Locksmith course London teaches vital security skills, while "Rust & Murderer" could refer to the blend of themes in video games like Rust, where survival is key. In Rust, players fend off threats and build secure shelters, mirroring real-life locksmith techniques. The "murderer" aspect might relate to challenges in these games, where players must be strategic, using stealth and cunning to outlast opponents. It emphasizes problem-solving, survival, and protection in virtual environments.

  • shanefostersmith
     + 0 comments

    Java solution below. BFS can be used for single source shortest distances in unweighted graphs, which is what this is. Build an adjacency list for city roads (since this graph is sparse, we'd want to be looking for nonexistence of city roads rather than existance of village roads during BFS, for efficiency). Keep track of unvisited nodes with a set.

    static int[] rustMurderer(int n, int[][] roads, int s) {
        
        // Build Adjacency List
        List<Set<Integer>> cityRoads = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            cityRoads.add(new HashSet<>());
        }
        int numRoads = roads.length;
        for (int i = 0; i < numRoads; i++) {
            int vertex1 = roads[i][0];
            int vertex2 = roads[i][1];
            cityRoads.get(vertex1 - 1).add(vertex2 - 1);
            cityRoads.get(vertex2 - 1).add(vertex1 - 1);
        }
        
        // Initialization for BFS
        int[] result = new int[n];
        result[s-1] = -1; // Use -1 to Indicate Source
        
        // Add Immediate Neighbors of Source to Queue
        Queue<Integer> BFSqueue = new LinkedList<>();
        Set<Integer> unvisited = new HashSet<>();
        for (int i = 1; i <=n; i++) {
            if (i != s) {
                if (!cityRoads.get(s-1).contains(i - 1)) {
                    //System.out.println("Source Neighbor Added =" + (i));
                    result[i - 1] = 1;
                    BFSqueue.add(i);
                } else {
                    unvisited.add(i);
                }
            }
        }
        
        // BFS for Shortest Dist
        int currentLevel = 1;
        while(!BFSqueue.isEmpty()) {
            int currentNode = BFSqueue.poll();
            
            // Not At Same Level as Before, Increment Level
            if (result[currentNode - 1] != currentLevel) {
                ++currentLevel;
            }
            //Add Valid Neighbors to Queue if Not Already Visited
            Iterator<Integer> currentUnvisited = unvisited.iterator();
            while (currentUnvisited.hasNext()) {
                int i = currentUnvisited.next();
                if (!cityRoads.get(currentNode-1).contains(i-1)) { // Can Go To This Node
                    result[i - 1] = currentLevel + 1;
                    BFSqueue.add(i);
                    currentUnvisited.remove();
                }
            }
        } 
        
        // Build Output Array and Return
        int[] output = new int[n-1];
        boolean passedS = false;
        for (int i = 0; i < n; i++) {
            if (result[i] == -1) {
                passedS = true;
                continue;
            }
            output[passedS ? i - 1 : i] = result[i];
        }
        return output;
    }

  • joinakhilesh
     + 1 comment

    For Solving this question here is my submission: 1- Find the adjacency list of compliment of the graph (this will be representing the village roads) 2- Run he BFS with shortest distance

    This is the simplest method in which this problem can be solved

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Rust & Murderer Problem Solution

  • mineman1012221
     + 0 comments

    Here is the solution of Rust & Murderer Click here