DarkNerd | ✅
Intuition:\n\nThe task is to compute the maximum number of nodes reachable from each node in the first graph within distance k while considering the maximum con
### Intuition:\n\nThe task is to compute the maximum number of nodes reachable from each node in the first graph within distance `k` while considering the maximum contribution from nodes in the second graph within distance `k-1`.  \nThis involves exploring the neighborhood of each node using BFS and combining results efficiently.\n\n---\n\n### Approach:\n\n1. **Parse Graphs from Edge Lists:**\n   - Construct adjacency lists for both graphs (`mp1` for `edges1` and `mp2` for `edges2`) using an unordered map.\n   - Track the maximum node indices in both graphs to determine the total number of nodes (`n` for the first graph and `m` for the second graph).\n\n2. **Breadth-First Search (BFS) Implementation:**\n   - Implement a BFS helper function that calculates the number of reachable nodes within a distance `k` from a starting node.\n   - Use a queue for level-wise traversal and a visited array to prevent revisiting nodes.\n\n3. **Calculate Reachable Nodes:**\n   - For each node in the first graph, calculate the number of reachable nodes within distance `k` using BFS and store results in `vec1`.\n   - Similarly, for each node in the second graph, calculate reachable nodes within distance `k-1` using BFS and store results in `vec2`.\n\n4. **Combine Results:**\n   - Find the maximum reachable nodes in `vec2`.\n   - For each node in the first graph, calculate the sum of reachable nodes from `vec1` and the maximum value from `vec2`, storing the result in the answer array `ans`.\n\n5. **Return the Result:**\n   - Return the `ans` array, which contains the maximum number of reachable nodes for each node in the first graph combined with the maximum from the second graph.\n\n---\n\n\n\n### Time Complexity:\n\n1. **Graph Construction:**\n   - Parsing the edges for both graphs takes $$O(E_1 + E_2)$$, where $$E_1$$ and $$E_2$$ are the number of edges in `edges1` and `edges2`.\n\n2. **BFS for Reachable Nodes:**\n   - For each node in both graphs, the BFS traversal takes $$O(V + E)$$ per graph, where $$V$$ is the number of nodes and $$E$$ is the number of edges. Across all nodes:\n     - First graph: $$O(n \\times (n + E_1))$$\n     - Second graph: $$O(m \\times (m + E_2))$$\n\n3. **Result Combination:**\n   - Finding the maximum in `vec2` and combining results for `ans` takes $$O(n + m)$$.\n\nOverall time complexity:  \n$$O(n^2 + m^2 + E_1 + E_2)$$\n\n---\n\n### Space Complexity:\n\n1. **Adjacency Lists:**\n   - Storage for adjacency lists `mp1` and `mp2`: $$O(E_1 + E_2)$$.\n\n2. **Visited Arrays:**\n   - BFS uses a visited array of size $$O(n)$$ for the first graph and $$O(m)$$ for the second graph.\n\n3. **Result Arrays:**\n   - Arrays `vec1`, `vec2`, and `ans` store $$O(n + m)$$ values.\n\nOverall space complexity:  \n$$O(n + m + E_1 + E_2)$$\n\n# Code\n```cpp []\nclass Solution {\n    int bfs(unordered_map<int, vector<int>>& mp, int node, int k, int n) {\n        if(k<0){\n            return 0;\n        }\n        vector<int> visited(n, 0);\n        queue<int> qu;\n        int ct = 1, level = 0;\n        qu.push(node);\n        visited[node] = 1;\n        while (!qu.empty() && level < k) {\n            int size = qu.size();\n            while (size-- > 0) {\n                int top = qu.front();\n                qu.pop();\n                for (int i : mp[top]) {\n                    if (visited[i]) {\n                        continue;\n                    }\n                    qu.push(i);\n                    visited[i] = 1;\n                    ct++;\n                }\n            }\n            level++;\n        }\n        return ct;\n    }\n\npublic:\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        unordered_map<int, vector<int>> mp1, mp2;\n        int n = 0, m = 0;\n\n        for (auto& edge : edges1) {\n            mp1[edge[0]].push_back(edge[1]);\n            mp1[edge[1]].push_back(edge[0]);\n            n = max({n, edge[0], edge[1]});\n        }\n        for (auto& edge : edges2) {\n            mp2[edge[0]].push_back(edge[1]);\n            mp2[edge[1]].push_back(edge[0]);\n            m = max({m, edge[0], edge[1]});\n        }\n\n        n++, m++;\n        vector<int> vec1(n, 0), vec2(m, 0);\n\n        for (int i = 0; i < n; i++) {\n            vec1[i] = bfs(mp1, i, k, n);\n        }\n        for (int i = 0; i < m; i++) {\n            vec2[i] = bfs(mp2, i, k-1, m);\n        }\n\n        vector<int> ans(n, 0);\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                ans[i] = max(ans[i], vec1[i] + vec2[j]);\n            }\n        }\n        return ans;\n    }\n};\n\n```
['C++']