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

  • 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;
    }