DFS with Detailed Explanation | Java |
Intuition\nThe problem is as follows: We are given two graphs or trees (referred to as graphs) with sizes n and m, respectively, and an integer k. We need to re
# Intuition\nThe problem is as follows: We are given two graphs or trees (referred to as graphs) with sizes `n` and `m`, respectively, and an integer `k`. We need to return an array of length `n`, where the `i-th` index in the array represents:\n\n*( The number of nodes that can be reached from the `i-th` node in `graph1` within a distance `k` ) plus `+`\n( The maximum number of nodes that can be reached in `graph2` from a single node in `graph2` within a distance `k\u22121`).*\n\n**Explanation of** "*the maximum number of nodes that can be reached in `graph2` from a node in `graph2` with distance `k\u22121`*":\n- This means we need to find a single node in `graph2` that can reach the maximum number of nodes in `graph2` within a distance `k\u22121`.\n \n- The `k\u22121` distance accounts for the fact that connecting a node in `graph2` to a node in `graph1` incurs a cost of 1 distance.\n\nWe must perform this calculation for every node in `graph1` and return the result as an array.\n\n**Observations**:\n- For any node in `graph1`, we need to account for the fact that it can always reach itself at a distance of `0`, which is less than or equal to `k`. Hence, if `k = 0`, we can simply return an array of all ones since no other nodes can be reached.\n\n- Why do we consider a single node in `graph2`? Because we can connect any node from `graph1` to `graph2`. To maximize the result, we simply need to find a single node in `graph2` that can reach the maximum number of nodes in `graph2` within a distance `k\u22121`. This ensures the optimal connection between the graphs.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Create two unidirectional graphs, `graph1` and `graph2`, based on the input edge arrays `edges1` and `edges2`.\n\n- Use either Depth First Search (**DFS**) or Breadth First Search (**BFS**) to find the node in `graph2` that can reach the maximum number of nodes within a distance `k\u22121`. Store this value as `max`.\n\n- For each node `i` in `graph1`, calculate the number of nodes it can reach within a distance `k` using **BFS** or **DFS**. Add this value to `max` and store the result in the answer array.\n\nThe final answer array will represent, for each node in `graph1`, the sum of:\n\n- The number of nodes reachable from the node in `graph1` within distance `k`, and\n\n- The maximum number of nodes reachable in `graph2` from a single node within distance `k\u22121`.\n\n# Complexity\n**Time complexity**:` O(V2 * (V2 + E2)) + O(V1 * (V1 + E1))`\n- O(V2 * (V2 + E2)) Computing the maximum reachable nodes in `graph2`.\n\n- O(V1 * (V1 + E1)) Computing the result for each node in `graph1`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n**Space complexity**: `O(V1 + E1 + V2 + E2 + K)`\n- O(V1 + E1) Storing `graph1`.\n\n- O(V2 + E2) Storing `graph2`.\n\n- O(K) Stack space for recursion.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {\n        int[] res = new int[edges1.length + 1];\n        if(k == 0) {\n            Arrays.fill(res, 1);\n            return res;\n        }\n        List<List<Integer>> graph1 = new ArrayList<>();\n        for(int i = 0; i < edges1.length + 1; ++i)\n            graph1.add(new ArrayList<>());\n\n        List<List<Integer>> graph2 = new ArrayList<>();\n        for(int i = 0; i < edges2.length + 1; ++i)\n            graph2.add(new ArrayList<>());\n        \n        for(int[] edge : edges1) {\n            graph1.get(edge[0]).add(edge[1]);\n            graph1.get(edge[1]).add(edge[0]);\n        }\n\n        for(int[] edge : edges2) {\n            graph2.get(edge[0]).add(edge[1]);\n            graph2.get(edge[1]).add(edge[0]);\n        }\n\n        boolean[] visited = new boolean[edges2.length + 1] ;\n        int max = 0;\n        for(int i = 0; i < edges2.length + 1; ++i) \n            max = Math.max(max, dfs(graph2, i, k - 1, visited));\n\n        visited = new boolean[edges1.length + 1] ;\n        for(int i = 0; i < edges1.length + 1; ++i) \n            res[i] = max + dfs(graph1, i, k, visited);\n\n        return res;\n    }\n    private int dfs(List<List<Integer>> list, int node, int k, boolean[] visited) {\n        if(k < 0) return 0;\n        int ans = 1;\n        visited[node] = true;\n        for(int cur: list.get(node)) \n            if(!visited[cur]) ans += dfs(list, cur, k - 1, visited);\n        visited[node] = false;\n        return ans;\n    }\n}\n```\n![OOGWAY my time has come.gif](https://assets.leetcode.com/users/images/68dfa2fd-d81b-4485-b529-8281d3592cdf_1733492431.8695526.gif)\n
['Java']