Easy to UnderStand || Begginer Friendly
Intuition\n\nThe problem involves two graphs represented by edge lists e1 and e2. The goal is to maximize the number of nodes reachable in the first graph, give
# Intuition\n\nThe problem involves two graphs represented by edge lists `e1` and `e2`. The goal is to maximize the number of nodes reachable in the first graph, given a constraint on the number of steps (`k`) that can be taken in the second graph.\n\nTo achieve this:\n1. Use `e2` to determine the maximum number of nodes reachable within `k-1` steps.\n2. Combine this with the result of iterating over `e1` for all possible starting points.\n\n---\n\n# Approach\n\n1. **Graph Construction**:\n   - Build adjacency lists for both graphs from `e1` and `e2`.\n\n2. **DFS Traversal**:\n   - Write a recursive function `IterateOnGraph` that performs a depth-first search (DFS) to calculate the number of nodes reachable from a given node within a specified number of steps (`k`).\n\n3. **Precompute Maximum Nodes in `G2`**:\n   - Iterate over all nodes in `G2` and calculate the maximum number of nodes reachable within `k-1` steps.\n\n4. **Calculate Results for `G1`**:\n   - For each node in `G1`, calculate the total number of reachable nodes by combining its DFS result with the precomputed maximum from `G2`.\n\n5. **Return Results**:\n   - Store the results for each node in `G1` in a vector and return it.\n\n---\n\n# Complexity\n\n- **Time Complexity**:\n  - **Graph Construction**: `O(n + m)`, where `n` is the number of nodes and `m` is the number of edges.\n  - **DFS Traversals**: `O(n  k)` for `G1` and `O(m  k)` for `G2`.\n  - Overall: `O((n + m)  k)`.\n\n- **Space Complexity**:\n  - Adjacency lists require `O(n + m)`.\n  - Recursive stack in DFS has a maximum depth of `k`.\n  - Overall: `O(n + m + k)`.\n\n---\n# Beats\n![image.png](https://assets.leetcode.com/users/images/22d76e9f-3642-4cf1-abc5-cbbf4b77a008_1733317295.0863006.png)\n\n---\n\n# Code\n\n```cpp\nclass Solution {\npublic:\n    // DFS function to calculate reachable nodes within \'k\' steps\n    int IterateOnGraph(int node, int parent, vector<vector<int>>& graph, int k) {\n        if (k <= 0) return (k == 0); // Base case: If no steps are left\n        int count = 1; // Count the current node\n        for (auto& neighbor : graph[node]) {\n            if (neighbor != parent) { // Avoid revisiting the parent node\n                count += IterateOnGraph(neighbor, node, graph, k - 1);\n            }\n        }\n        return count;\n    }\n\n    vector<int> maxTargetNodes(vector<vector<int>>& e1, vector<vector<int>>& e2, int k) {\n        int n1 = e1.size() + 1, n2 = e2.size() + 1;\n        vector<vector<int>> G1(n1), G2(n2);\n\n        // Construct adjacency lists for both graphs\n        for (auto& edge : e1) {\n            G1[edge[0]].push_back(edge[1]);\n            G1[edge[1]].push_back(edge[0]);\n        }\n        for (auto& edge : e2) {\n            G2[edge[0]].push_back(edge[1]);\n            G2[edge[1]].push_back(edge[0]);\n        }\n\n        // Precompute the maximum reachable nodes in G2 within k-1 steps\n        int maxG2 = 0;\n        for (int i = 0; i < n2; i++) {\n            maxG2 = max(maxG2, IterateOnGraph(i, -1, G2, k - 1));\n        }\n\n        // Calculate results for G1\n        vector<int> result;\n        for (int i = 0; i < n1; i++) {\n            result.push_back(IterateOnGraph(i, -1, G1, k) + maxG2);\n        }\n\n        return result;\n    }\n};\n```\n\n---\n\n# Explanation of the Code\n\n1. **Graph Construction**:\n   - Convert `e1` and `e2` edge lists into adjacency lists `G1` and `G2`.\n\n2. **DFS Traversal**:\n   - `IterateOnGraph` is a recursive function that counts all nodes reachable from a given starting point within `k` steps.\n\n3. **Maximizing Nodes in `G2`**:\n   - Iterate over all nodes in `G2` and calculate the maximum nodes reachable within `k-1` steps.\n\n4. **Combining Results**:\n   - For each node in `G1`, calculate the total nodes reachable by summing its DFS result and the precomputed maximum for `G2`.\n\n5. **Result**:\n   - Store the total for each node in `G1` and return as the output.\n\n---\n\n# Edge Cases\n\n1. **Disconnected Graph**:\n   - If some nodes are not connected in `G1` or `G2`, ensure the result accounts for isolated nodes.\n\n2. **Small `k`**:\n   - For \\(k = 1\\), only the current node can be considered in `G1`.\n\n3. **No Edges**:\n   - If `e1` or `e2` is empty, the graphs will only have isolated nodes.
['Tree', 'Depth-First Search', 'C++']