[Leetcode]928. Minimize Malware Spread II

Title address:

https://leetcode.com/problems/minimize-malware-spread-ii/

Given a n n An undirected graph with n nodes is given by adjacency matrix. Each node represents a node in a network. Give another array A A A, A [ i ] A[i] A[i] indicates the node i i i was infected (hereinafter referred to as A A The point in A is "infection source". When A node is infected, all nodes of its connected block will be infected. Now it is allowed to select an "infection source" and delete it (after deleting, the infection source and all its adjacent edges will be deleted). Ask which node can be deleted to minimize the total number of infected nodes of the remaining nodes. If there are multiple answers, the node with the lowest number is returned.

This question can be related to https://blog.csdn.net/qq_46105170/article/details/113488695 Together, the two solutions can learn from each other.

You can use and query sets. We should mainly consider how many nodes can be "saved" after deleting an infection source. We can ignore the infection source first, and then use the union search set to count the connected blocks. Next, we use the hash table to count how many infection sources have infected each connected block, and skip the uninfected connected blocks if they are infected more than 1 1 If one infection source is infected, no matter which infection source is deleted, the connection block cannot be saved, and such connection block is not considered; If it happens to be 1 1 If one infection source is infected, the number of nodes that can be saved by deleting the infection source is the number of connected block elements. We enumerate each infection source, then see how many nodes can be saved by deleting it, and find the infection source that can save the most nodes. If the answer is not unique, find the one with the smallest number. The code is as follows:

import java.util.*;

public class Solution {
    
    class UnionFind {
        int[] parent, size;
        
        public UnionFind(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
            this.size = new int[size];
            Arrays.fill(this.size, 1);
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public void union(int x, int y) {
            int px = find(x), py = find(y);
            if (px == py) {
                return;
            }
            
            parent[px] = py;
            size[py] += size[px];
        }
    }
    
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        // Record which points are the source of infection
        boolean[] dirty = new boolean[n];
        for (int x : initial) {
            dirty[x] = true;
        }
        
        // Regardless of the source of infection, find the connecting block
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            if (!dirty[i]) {
                for (int j = i + 1; j < n; j++) {
                    if (!dirty[j] && graph[i][j] == 1) {
                        uf.union(i, j);
                    }
                }
            }
        }
        
        // Find out which infection sources infect each connected block. key stores the tree root of the connected block, and value stores the number of infection sources that can infect the connected block
        Map<Integer, Set<Integer>> infectorMap = new HashMap<>();
        for (int x : initial) {
            for (int y = 0; y < graph[x].length; y++) {
            	// If you can infect y through x, save it with a hash table
                if (!dirty[y] && graph[x][y] == 1) {
                    int py = uf.find(y);
                    infectorMap.putIfAbsent(py, new HashSet<>());
                    infectorMap.get(py).add(x);
                }
            }
        }
        
        // Find out how many nodes can be saved if each infection source is deleted.
        // Note that the connecting blocks infected by multiple infection sources should be omitted here. These connecting blocks cannot be saved
        Map<Integer, Integer> saveCount = new HashMap<>();
        for (Map.Entry<Integer, Set<Integer>> entry : infectorMap.entrySet()) {
            int parent = entry.getKey();
            Set<Integer> infectors = entry.getValue();
            // If the current connection block is infected by multiple infection sources, skip it
            if (infectors.size() > 1) {
                continue;
            }
            
            // Add up how many nodes can be saved if the infection source is deleted
            int infector = infectors.iterator().next();
            saveCount.put(infector, saveCount.getOrDefault(infector, 0) + uf.size[parent]);
        }
        
        // If each connected block is infected by more than one infection source, delete the infection source with the smallest number
        if (saveCount.isEmpty()) {
            int res = n;
            for (int i : initial) {
                res = Math.min(res, i);
            }
            
            return res;
        }
        
        // Otherwise, find the infection source with the most saved nodes
        int res = -1, maxSave = 0;
        for (Map.Entry<Integer, Integer> entry : saveCount.entrySet()) {
            int infector = entry.getKey(), saved = entry.getValue();
            if (saved > maxSave) {
                maxSave = saved;
                res = infector;
            } else if (saved == maxSave) {
                res = Math.min(res, infector);
            }
        }
        
        return res;
    }
}

Time complexity O ( n 2 log ⁡ ∗ n ) O(n^2\log ^* n) O(n2log * n), space O ( n ) O(n) O(n).

Tags: data structure leetcode Graph Theory dfs Hash table

Posted by msarefin on Tue, 26 Apr 2022 09:58:44 +0300