Java Union Find with Explanation
Intuition\nLoop through inital array and perform the following where each node in initial is removed one at a time:\n\nUnion find, finds a unique parent of ever
# Intuition\nLoop through inital array and perform the following where each node in initial is removed one at a time:\n\nUnion find, finds a unique parent of every node. If parent of a normal node is a parent of an infected node, it must be in the same disjoint set, hence it is infected. Place parents of infected nodes in a set. Check each node, if its parent is apart of set, it is infected. return index of the node that if removed minimises M.\n\n# Complexity\n- Time complexity:\nloops through initial array -> O(k)\n\nCreate union set, find() is log(n) -> O(E * log(n))\nloop through all nodes find parent (this call of find() is O(1) as the path has already been compressed) -> O(n)\n\ntotal: O(k(E * log(n) + n))\n\n# Code\n```\nclass Solution {\n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        // storing minimiser and M value at minimiser\n        int minimiser = -1;\n        int min_val = Integer.MAX_VALUE;\n\n\n        for (int i = 0; i < initial.length; i++) {\n\n            // for given infected node find M value if it is removed\n            int rem_val = singleInitRem(graph, initial, initial[i]);\n\n            // second statement for finding lower node index on ties for M value\n            if (rem_val < min_val || (rem_val == min_val && minimiser > initial[i])) {\n                min_val = rem_val;\n                minimiser = initial[i];\n            }\n\n        }\n        return minimiser;\n    }\n\n    public int singleInitRem(int[][] graph, int[] init, int rem) {\n\n        int n = graph.length;\n        UF uf = new UF(n);\n\n        // creating union find set, skip node (rem) that is removed\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                if (i == rem || j == rem || graph[i][j] == 0) continue;\n                \n                uf.union(i, j);\n            }\n        }\n\n        // finding parents of infected nodes, if any other node is connected\n        // it is joint to an infected set\n        HashSet<Integer> infected_parents = new HashSet<>();\n        for (int i = 0; i < init.length; i++) {\n            if (init[i] == rem) continue;\n\n            infected_parents.add(uf.find(init[i]));\n        }\n\n        // finding infected nodes, skipping removed node\n        int infected = 0;\n        for (int i = 0; i < n; i++) {\n            if (i == rem) continue;\n\n            if (infected_parents.contains(uf.find(i))) infected++;\n        }\n        return infected;\n    }\n\n    // classical union find with compression (use rank based for better performance)\n    public class UF {\n        int n;\n        int[] parent;\n\n        public UF(int n) {\n            parent = new int[n];\n            for (int i = 0; i < n; i++) {\n                parent[i] = i;\n            }\n        }\n\n        public void union(int i, int j) {\n            int par_j = find(j), par_i = find(i);\n            parent[par_i] = par_j;\n        }\n\n        public int find(int i) {\n            if (parent[i] == i) { \n                return i; \n            } \n            parent[i] = find(parent[i]); \n            return parent[i]; \n            \n        }\n\n    }\n}\n```
['Java']