C++ | BruteForce | BFS |
Intuition\nwe need at most k distance count of nodes for tree1 and maximum distance cout for any node in tree2 we will just add the count from tree1 to max of t
# Intuition\nwe need at most k distance count of nodes for tree1 and maximum distance cout for any node in tree2 we will just add the count from tree1 to max of tree2\n\n# Approach\nuse bfs to count k distance nodes\n\n# Complexity\n- Time complexity:\nO(N * N + M * M)\n\n- Space complexity:\nO(N + M);\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    int bfs (int root, vector<vector<int>>& adj, int k) {\n\n      queue<int> q;\n      q.push(root);\n      vector<bool> vis(1001, false);\n      int level = 0, res = 1;\n      while (!q.empty() && level < k) {\n        level++;\n        int sz = q.size();\n        for (int i = 0; i < sz; i++) {\n          int node = q.front();\n          q.pop();\n          vis[node] = true;\n          for (auto nbr : adj[node]) {\n            if (vis[nbr] == false)\n              res++, q.push(nbr);\n          }\n        }\n      }\n      return res;\n    }\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        \n      ios::sync_with_stdio(false);\n      cin.tie(0); cout.tie(0);\n      vector<vector<int>> adj1(edges1.size() + 1), adj2(edges2.size() + 1);\n      for (int i = 0; i < edges1.size(); i++) {\n        adj1[edges1[i][0]].push_back(edges1[i][1]);\n        adj1[edges1[i][1]].push_back(edges1[i][0]);\n      }\n      for (int i = 0; i < edges2.size(); i++) {\n        adj2[edges2[i][0]].push_back(edges2[i][1]);\n        adj2[edges2[i][1]].push_back(edges2[i][0]);\n      }\n      int mx = 0;\n      for (int i = 0; i < adj2.size(); i++) {\n        mx = max(mx, bfs(i, adj2, k - 1));\n      }\n      vector<int> res(edges1.size() + 1, 0);\n      for (int i = 0; i < adj1.size(); i++) {\n        if (k == 0)\n          res[i] = 1;\n        else\n          res[i] = (mx + bfs(i, adj1, k));\n      }\n      return res;\n\n    }\n};\n```
['C++']