Java | Union Find | Explained
Approach Use Disjoint Set Union with Path compression\n\n>T/S: O(n\xB2)/O(n), where n = size(graph)\n\npublic int minMalwareSpread(int[][] graph, int[] initial)
**Approach** Use Disjoint Set Union with Path compression\n\n>T/S: O(n\xB2)/O(n), where n = size(graph)\n```\npublic int minMalwareSpread(int[][] graph, int[] initial) {\n    var maxSize = 0;\n    var ans = -1;\n    var n = graph.length;\n    var parent = new int[n];\n    var size = new int[n];\n    var infected = new int[n];\n    var initialSet = new HashSet<Integer>();\n    var infectedToConnectedComponentsParents = new HashMap<Integer, Set<Integer>>();\n\n    init(initial, initialSet, infectedToConnectedComponentsParents);\n    Arrays.setAll(parent, i -> i);\n    Arrays.fill(size, 1);\n\n    // Create components without the infected nodes\n    for (var i = 0; i < n; i++)\n        for (var j = 0; j < n; j++)\n            if (i != j && graph[i][j] == 1 && !initialSet.contains(i) && !initialSet.contains(j)) {\n\n                var parentI = find(parent, i);\n                var parentJ = find(parent, j);\n\n                if (parentI != parentJ)\n                    union(size, parent, parentI, parentJ);\n            }\n\n    /*\n    * Create a map of infected nodes (I) to parents of components which contain neighbors of I.\n    * This is done to find out how many nodes we can save from getting infected if we delete I\n    * This is also the reason we exclude counting any neighbor of I which itself is infected because deletion of I\n    cannot save an originally infected node\n\n    * Additionally, we also keep count of how many times a parent appears in different components.\n    * If infected[parent = P] = 1, then it means P is part of only 1 component which has only 1 infected node\n    * If infected[parent = P] > 1, then removing one infected node will not make any difference because there are\n    * other infected nodes which can infect the whole component. Thus skip such components\n    */\n    for (var i : initial)\n        for (var j = 0; j < n; j++)\n            if (i != j && graph[i][j] == 1 && !initialSet.contains(j)) {\n                var parentJ = find(parent, j);\n\n                if (infectedToConnectedComponentsParents.get(i).add(parentJ))\n                    infected[parentJ]++;\n            }\n\n    /*\n    * Now iterate through all infected nodes I\n    * Then iterate through all disinfectable components that node-I effects and sum up their sizes (S). This is done to \n    find out how many nodes can get disinfected if we remove I\n    * Find max S among all sums and the corresponding I will be the answer\n    * In case of a tie, choose min(I)\n    * If no result is found, min(initial) is the answer           \n    */\n    for (var i : initial) {\n        var componentSize = 0;\n\n        for (var head : infectedToConnectedComponentsParents.get(i))\n            if (infected[head] == 1)\n                componentSize += size[head];\n\n        if (maxSize == componentSize) {\n            ans = Math.min(ans, i);\n        } else if (maxSize < componentSize) {\n            ans = i;\n            maxSize = componentSize;\n        }\n    }\n\n    return ans == -1\n         ? Arrays.stream(initial).min().getAsInt()\n         : ans;\n}\n\nprivate void init(int[] initial, Set<Integer> set, Map<Integer, Set<Integer>> map) {\n    for (var i : initial) {\n        set.add(i);\n        map.put(i, new HashSet<>());\n    }\n}\n\nprivate int find(int[] parent, int i) {\n    if (parent[i] == i)\n        return i;\n    return parent[i] = find(parent, parent[i]);\n}\n\nprivate void union(int[] size, int[] parent, int i, int j) {\n    if (size[j] < size[i]) {\n        parent[j] = i;\n        size[i] += size[j];\n    } else {\n        parent[i] = j;\n        size[j] += size[i];\n    }\n}\n```\n***Please upvote if this helps***
['Java']