BFS Solution || Detailed Explanation || C++ || Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nTo determine the maximum number of nodes that can be reached within a distance k in two
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo determine the maximum number of nodes that can be reached within a distance `k` in two graphs, we can use Breadth-First Search (BFS). BFS is ideal for exploring nodes layer by layer, making it easy to track nodes within a limited distance. By leveraging BFS, we can count reachable nodes in one graph and use this result to enhance counts from the other graph.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Adjacency List Construction:\n    - Convert edges1 and edges2 into adjacency lists (adj1 and adj2) to represent the graphs.\n    - Add edges as bidirectional to simulate undirected graphs.\n\n2. BFS Implementation:\n    - For a given start node, BFS explores nodes level by level, maintaining a count of reachable nodes and using a distance limit (k).\n    - Use a visited array to prevent revisiting nodes.\n\n3. Compute Maximum BFS Count for Graph 2:\n    - Iterate over all nodes in adj2 and compute the maximum count of reachable nodes within k-1 distance.\n\n4. Combine Results for Graph 1:\n    - For each node in adj1, perform BFS up to distance k and add the maximum count from adj2.\n\n5. Return Results:\n    - The result array contains combined counts for each node in adj1.\n# Complexity\n- Time complexity:$$O(V1\u22C5(E1/V1+k)+V2\u22C5(E2/V2+k))$$\n    - BFS runs for each node in both graphs, iterating over edges.\n    - Let V1 and E1 be the vertices and edges in edges1, and V2 and E2 in edges2. \n    - $$O(V1\u22C5(E1/V1+k)+V2\u22C5(E2/V2+k))$$, approximately linear in nodes and edges. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n    - BFS uses a queue (O(V)), a visited array (O(V)), and adjacency lists (O(E)), where V and E depend on the graph size.\n    - O(V1+E1+V2+E2) in total. \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    int BfsCount(vector<vector<int>>& adj,int k,int start,int size){\n        queue<int> q;\n        q.push(start);\n        vector<bool> visited(size,false);\n        visited[start] = true;\n        int count = 0;\n        int dist = 0;\n\n        while(!q.empty() && dist<=k){\n            int qs = q.size();\n            for(int i=0;i<qs;i++){\n                int Node = q.front();\n                q.pop();\n                count++;\n                for(auto it: adj[Node]){\n                    if(!visited[it]){\n                        visited[it] = true;\n                        q.push(it);\n                    }\n                }\n            }\n            \n            dist++;\n        }\n        return count;\n    }\n\npublic:\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        int n = edges1.size()+1;\n        int m = edges2.size()+1;\n        vector<vector<int>> adj1(n), adj2(m);\n        for(const auto& it: edges1){\n            adj1[it[0]].push_back(it[1]);\n            adj1[it[1]].push_back(it[0]);\n        }\n\n        for(const auto& it: edges2){\n            adj2[it[0]].push_back(it[1]);\n            adj2[it[1]].push_back(it[0]);\n        }\n\n        int max_BfsCount_v = 0;\n\n        for(int i=0;i<m;i++){\n            int cnt = BfsCount(adj2,k-1,i,m);\n            if(cnt> max_BfsCount_v) max_BfsCount_v = cnt;\n        }\n\n        vector<int> ans(n);\n        for(int i=0;i<n;i++){\n            ans[i] = BfsCount(adj1,k,i,n)+max_BfsCount_v;\n        }\n\n        return ans;\n    }\n};\n```
['Tree', 'Breadth-First Search', 'C++']