[Java] 3 clean codes: DFS, Union Find and Tarjan's algorithm
DFS\n\nApproach: For each initial node, do a DFS of the graph and count how many nodes would get saved if this node was not there.\nOptimization 1: Since removi
**DFS**\n\n**Approach:** For each initial node, do a DFS of the graph and count how many nodes would get saved if this node was not there.\n**Optimization 1:** Since removing this node can only affect the fate of nodes in its connected component, do a DFS only over nodes connected to this node.\n**Optimization 2:** If we encounter another initial node during a DFS, then we mark all the nodes in the path as infected too. Remember, we started from an infected node and now we have encounted another infected node so this means that no matter what, the nodes in between are doomed to get infected eventually (removing any one of the initial nodes isn\'t going to save them).\n\n```\n// 2 ms. 92.26%\nclass Solution {\n    private int dfs(int[][] graph, int u, boolean[] visited, boolean[] infected) {\n        if(infected[u]) return 0;\n        visited[u] = true;\n        int count = 1;\n        for(int v = 0; v < graph[u].length; v++) {\n            if(!visited[v] && graph[u][v] == 1) {\n                int c = dfs(graph, v, visited, infected);\n                if(c == 0) {\n                    infected[u] = true;\n                    return 0;\n                }\n                count += c;\n            }\n        }\n        return count;\n    }\n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        int n = graph.length, ans = initial[0], max = 0;\n        boolean[] infected = new boolean[n];\n        for(int u: initial) infected[u] = true;\n        for(int u: initial) {\n            boolean[] visited = new boolean[n];\n            visited[u] = true;\n            int count = 0;\n            for(int i = 0; i < n; i++) {\n                if(!visited[i] && graph[u][i] == 1) {\n                    count += dfs(graph, i, visited, infected);\n                }\n            }\n            if(count > max || count == max && u < ans) {\n                max = count;\n                ans = u;\n            }\n        }\n        return ans;\n    }\n}\n```\n\nTime complexity: O(K N<sup>2</sup>) where N = number of total nodes and K = number of initially infected nodes.\nSpace complexity: O(N)\n\n**Disjoint Set / Union Find**\n\n**Approach:**\nFirst we identify the connected components in the graph without considering infected nodes. Then we consider each infected node one by one and check how many components are connected to it if we were to add this node (and its edges) into the graph. After having processed all the nodes, we iterate over infected nodes again to see which connected components are exclusively affected by a single infected node because that\'s the component which\'ll get saved on removing that infected node. (If a component is connected to multiple infected nodes, removing only one of the infected nodes is not going to save it.)\n\n[Union-Find or Disjoint-Set](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) is a perfect data structure for our use case of efficiently adding nodes (and their edges) one by one and to keep track of connected components and their sizes.\n\n\n```\n// 6 ms. 66.45%\nclass Solution {\n    class UnionFind {\n        public int[] parent, size;\n        UnionFind(int n) {\n            parent = new int[n];\n            size = new int[n];\n            for(int i = 0; i < n; i++) {\n                parent[i] = i;\n                size[i] = 1;\n            }\n        }\n        public int find(int x) {\n            return x != parent[x] ? x = find(parent[x]) : x;\n        }\n        public void union(int x, int y) {\n            int a = find(x), b = find(y);\n            if(a != b) {\n                if(size[a] < size[b]) {\n                    parent[a] = b;\n                    size[b] += size[a];\n                } else {\n                    parent[b] = a;\n                    size[a] += size[b];\n                }\n            }\n        }\n    }\n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        int n = graph.length, ans = initial[0], max = 0;\n        boolean[] infected = new boolean[n];\n        for(int u: initial) infected[u] = true;\n        UnionFind uf = new UnionFind(n);\n        for(int i = 0; i < n; i++) {\n            if(!infected[i]) {\n                for(int j = i + 1; j < n; j++) {\n                    if(!infected[j] && graph[i][j] == 1) uf.union(i, j);\n                }\n            }\n        }\n        int[] count = new int[n];\n        Set<Integer>[] component = new Set[n];\n        for(int u: initial) {\n            component[u] = new HashSet<>();\n            for(int v = 0; v < n; v++) {\n                if(!infected[v] && graph[u][v] == 1) component[u].add(uf.find(v));\n            }\n            for(int v: component[u]) count[v]++;\n        }\n        for(int u: initial) {\n            int save = 0;\n            for(int v: component[u]) {\n                if(count[v] == 1) save += uf.size[v];\n            }\n            if(save > max || save == max && u < ans) {\n                max = save;\n                ans = u;\n            }\n        }\n        return ans;\n    }\n}\n```\n\nTime complexity: O(N<sup>2</sup>)\nSpace complexity: O(N)\n\n**Tarjan\'s algorithm**\n\n**Approach:** We can apply [Tarjan\'s algorithm](https://en.wikipedia.org/wiki/Biconnected_component) to find all the articulation points in the graph in O(V + E) time via a DFS. An articulation point is a node removing which disconnects the graph. At the time of identifying whether a node is an articulation point or not, the algorithm also (automatically?) tells us precisely which DFS subtree (or biconnected component) would get disconnected from the graph if we were to remove this node. We can use this information to solve our problem i.e. if that subtree does not contain any other initially infected nodes, then it is clear that removing this node is going to save that entire subtree otherwise it doesn\'t matter, that subtree is doomed anyway. So all we need to do extra (apart from the usual stuff for Tarjan\'s algo) is to make DFS method return the size of the connected component when there are no infected nodes in it otherwise 0.\n\n```\n// 2 ms. 92.26%\nclass Solution {\n    private int dfs(int[][] graph, int u, int parent, int time, int[] depth, int[] low, boolean[] infected, int[] count) {\n        low[u] = depth[u] = time;\n        boolean flag = infected[u];\n        int size = 1;\n        for(int v = 0; v < graph[u].length; v++) {\n            if(graph[u][v] == 1) {\n                if(depth[v] == 0) {\n                    int s = dfs(graph, v, u, time + 1, depth, low, infected, count);\n                    if(s == 0) {\n                        flag = true;\n                    } else {\n                        size += s;\n                    }\n                    if(low[v] >= depth[u]) {\n                        count[u] += s;\n                    }\n                    low[u] = Math.min(low[u], low[v]);\n                } else if(v != parent) {\n                    low[u] = Math.min(low[u], depth[v]);\n                }\n            }\n        }\n        return flag ? 0 : size;\n    }\n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        int n = graph.length, ans = initial[0], max = 0;\n        boolean[] infected = new boolean[n];\n        for(int u: initial) infected[u] = true;\n        int[] depth = new int[n], low = new int[n], count = new int[n];\n        for(int u: initial) {\n            if(depth[u] == 0) {\n                dfs(graph, u, -1, 1, depth, low, infected, count);\n            }\n            if(count[u] > max || count[u] == max && u < ans) {\n                max = count[u];\n                ans = u;\n            }\n        }\n        return ans;\n    }\n}\n```\n\nTime complexity: O(N<sup>2</sup>)\nSpace complexity: O(N)
['Java']