3372. Maximize the Number of Target Nodes After Connecting Trees I | DFS Solution ✨✅
\uD83C\uDF33 Connecting Two Trees with a Limit - Intuition and Approach Explained\n\n## Intuition\n\nThe problem revolves around two trees with n and m nodes an
# \uD83C\uDF33 **Connecting Two Trees with a Limit - Intuition and Approach Explained**\n\n## **Intuition**\n\nThe problem revolves around **two trees** with `n` and `m` nodes and asks us to compute how many nodes from both trees can be reached from a node in the first tree with a **distance limit of k edges**.  \n\n- A node in the second tree is only reachable if we consider connecting one node from the first tree to it.  \n- We need to efficiently compute the **maximum number of reachable nodes** from each node in the first tree, considering this **virtual connection**.\n\nThe approach leverages **Depth-First Search (DFS)** to calculate reachable nodes and ensures that the operations are performed efficiently on the given graphs.\n\n---\n\n## **Approach**\n\n### **Step-by-Step Solution**\n\n1. **Graph Representation:**\n   - Use adjacency lists (`graph1` and `graph2`) to represent the two trees, making traversal straightforward.\n\n2. **DFS Traversal:**\n   - Implement a recursive DFS function that counts how many nodes can be reached from a given node within `k` edges.\n   - If the path length exceeds `k`, terminate the DFS for that path.\n\n3. **Pre-computation for Tree 2:**\n   - Compute the **maximum reachable nodes** from any node in the second tree (`tree2`) with `k-1` edges.  \n   - This helps as every query node in the first tree will benefit from connecting to this optimized configuration of the second tree.\n\n4. **Query Each Node in Tree 1:**\n   - For each node in the first tree, perform a DFS to calculate how many nodes can be reached within `k` edges.\n   - Add the precomputed maximum from the second tree to this count.\n\n5. **Result Compilation:**\n   - Store the computed values for each node in the first tree in an array and return the result.\n\n---\n\n## **Complex Coding Topics Simplified**\n\n### **1. DFS in Trees**\n   - DFS is ideal for traversing nodes connected in a graph/tree structure.\n   - It uses a **recursive backtracking approach**, marking nodes as visited to avoid revisits.\n\n### **2. Pre-computation**\n   - By calculating the best possible result for the second tree independently, we save repeated calculations during queries for the first tree.\n\n---\n\n## **Code Explanation**\n\n```cpp\n#define vi vector<int>\n#define vvi vector<vi>\n\nclass Solution {\npublic:\n    // Helper DFS function to count reachable nodes within the distance `k`.\n    int dfs(int node, int cnt, vvi &graph, vector<bool> &vis, int k) {\n        // If the current path exceeds the distance limit, terminate.\n        if (cnt > k) return 0;\n\n        vis[node] = true;  // Mark the current node as visited.\n        int count = 1;     // Count the current node.\n\n        // Traverse all connected nodes.\n        for (int neighbor : graph[node]) {\n            if (!vis[neighbor]) {\n                count += dfs(neighbor, cnt + 1, graph, vis, k);\n            }\n        }\n\n        return count;  // Return the total count of reachable nodes.\n    }\n\n    // Helper function to compute the best possible result for the second tree.\n    int help(int m, vvi &graph2, int k) {\n        int maxNodes = 0;\n\n        // Iterate over all nodes in the second tree.\n        for (int i = 0; i < m; ++i) {\n            vector<bool> vis(m, false);  // Reset visited nodes for each DFS call.\n            int reachable = dfs(i, 0, graph2, vis, k - 1);  // Max reach within k-1.\n            maxNodes = max(maxNodes, reachable);  // Update the maximum.\n        }\n\n        return maxNodes;  // Return the best possible result for the second tree.\n    }\n\n    // Main function to calculate the result for all nodes in the first tree.\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, \n                               vector<vector<int>>& edges2, int k) {\n        int n = edges1.size() + 1, m = edges2.size() + 1;\n\n        // Build adjacency lists for both trees.\n        vvi graph1(n), graph2(m);\n        for (vector<int> &edge : edges1) {\n            graph1[edge[0]].push_back(edge[1]);\n            graph1[edge[1]].push_back(edge[0]);\n        }\n\n        for (vector<int> &edge : edges2) {\n            graph2[edge[0]].push_back(edge[1]);\n            graph2[edge[1]].push_back(edge[0]);\n        }\n\n        // Precompute the best result for the second tree.\n        int tree2Result = help(m, graph2, k);\n\n        vector<int> result;  // To store results for all nodes in the first tree.\n\n        // Query each node in the first tree.\n        for (int i = 0; i < n; ++i) {\n            vector<bool> vis(n, false);  // Reset visited nodes for each DFS call.\n            int reachable = dfs(i, 0, graph1, vis, k);  // Max reach in the first tree.\n            reachable += tree2Result;  // Add the precomputed result from the second tree.\n            result.push_back(reachable);\n        }\n\n        return result;  // Return the result array.\n    }\n};\n```\n\n---\n\n## **Complexity Analysis**\n\n1. **Time Complexity:**\n   - **Graph Construction:** \\( O(n + m) \\), where \\( n \\) and \\( m \\) are the number of nodes in the two trees.\n   - **DFS Traversals:**\n     - For Tree 1: \\( O(n * k) \\), as each DFS explores up to \\( k \\) edges.\n     - For Tree 2: \\( O(m * k) \\).\n   - **Overall:** \\( O(n * k + m * k) \\).\n\n2. **Space Complexity:**\n   - **Graph Storage:** \\( O(n + m) \\) for adjacency lists.\n   - **Visited Array:** \\( O(max(n, m)) \\).\n   - **Overall:** \\( O(n + m) \\).\n\n---\n\n# **PLEASE UPVOTE IF YOU LIKED IT \u2705**
['C++']