✅✅✅Easy To Understand C++ Code||BFS
Intuition\n Describe your first thoughts on how to solve this problem. \nbrute force :finding answer for every node independently as constraints are too low.\n#
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nbrute force :finding answer for every node independently as constraints are too low.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUsing bfs finding how many nodes can be reached from every other node for tree1 .\nNow, we need to draw one edge from tree1 to tree2 we will greedily find which node of tree2 can traverse to maximum number of nodes to a max distance of k-1 as 1 distance will be used in connecting 2 trees\nnow adding this ans in every node of tree1 \n# Code\n```cpp []\nclass Solution {\npublic:\n    int bfs(vector<int>adj[],int k,int node,int n){\n        queue<int>q;\n        vector<bool>vis(n,false);\n        int cnt=k>=0?1:0;\n        // if k is less than 0 we can\'t travel from any of the node \n        q.push(node);\n        vis[node]=1;\n        while(!q.empty() && k>0){\n           int size=q.size();\n           while(size--){\n            int x=q.front();q.pop();\n            for(auto it:adj[x]){\n                if(!vis[it]){\n                    vis[it]=1;\n                    q.push(it);\n                    cnt++;\n                }\n             }\n           }\n          k--;\n        }\n        return cnt;\n    }\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        int n=edges1.size(),m=edges2.size(),maxi=0;\n        vector<int>adj1[n+1],adj2[m+1];\n        // creating adjacency for graph1\n        for(auto it:edges1){\n            adj1[it[0]].push_back(it[1]);\n            adj1[it[1]].push_back(it[0]);\n        }\n        // creating adjacency for graph2\n        for(auto it:edges2){\n            adj2[it[0]].push_back(it[1]);\n            adj2[it[1]].push_back(it[0]);\n        }\n        //finding the node with greatest travel capacity in graph2\n        for(int i=0;i<=m;i++){\n            maxi=max(maxi,bfs(adj2,k-1,i,m+1));\n        }\n        //findind total number of nodes at\n        // a distance of k and adding nodes of graph2 \n        vector<int>ans(n+1);\n        for(int i=0;i<=n;i++){\n            ans[i]=bfs(adj1,k,i,n+1)+maxi;\n        }\n        return ans;\n    }\n};\n```
['Tree', 'Breadth-First Search', 'C++']