C++ | BFS Simple approach
Intuition\nThis one i couldn\'t solve in contest but the approach i was thinking around was quite right.\nWe can calculate cnt of nodes who are at lesser then o
# Intuition\nThis one i couldn\'t solve in contest but the approach i was thinking around was quite right.\nWe can calculate cnt of nodes who are at lesser then or equal to k distance from me and then make a count array for both the graphs seperately.After that we simply add them at each index because when we join a node with an edge to other graph just 1 edge is added extra which is 1 dist. So if we calculate nodes lesser then k-1 for graph 2 it would become lesser then equal to k. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nO(n*(n+E)+m*(m+E))\n\n- Space complexity:\nO(n+m)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int shortestPath(int src,vector<vector<int>>adj,int N,int k){\n        if(k<0)return 0;\n        //bfs traversal to determine all least distances\n        queue<pair<int,int>>q;\n        q.push({0,src});\n        int cnt=1;\n        \n        vector<int>vis(N,0);\n        vis[src]=1;\n        while(!q.empty()){\n            auto it=q.front();\n            int node=it.second;\n            int dist=it.first;\n            q.pop();\n            // if(dist<=k)\n            for(auto it:adj[node]){\n                if(dist+1<=k && !vis[it]){\n                    vis[it]=1;\n                    cnt++;\n                    q.push({dist+1,it});\n                }\n            }\n        }\n        return cnt;\n    }\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        int maxNode1 = 0, maxNode2 = 0;\n        for (auto& edge : edges1) {\n            maxNode1 = max(maxNode1, max(edge[0], edge[1]));\n        }\n        for (auto& edge : edges2) {\n            maxNode2 = max(maxNode2, max(edge[0], edge[1]));\n        }\n        int n=edges1.size();\n        int m=edges2.size();\n        // Create adjacency lists for both graphs.\n        // vector<vector<int>> adj1(maxNode1 + 1);\n        // vector<vector<int>> adj2(maxNode2 + 1);\n        vector<vector<int>> adj1(n + 1);\n        vector<vector<int>> adj2(m + 1);\n\n        // Build adjacency list for graph 1.\n        for (auto& edge : edges1) {\n            adj1[edge[0]].push_back(edge[1]);\n            adj1[edge[1]].push_back(edge[0]);\n        }\n\n        // Build adjacency list for graph 2.\n        for (auto& edge : edges2) {\n            adj2[edge[0]].push_back(edge[1]);\n            adj2[edge[1]].push_back(edge[0]);\n        }\n        // int n=maxNode1,m=maxNode2;\n        vector<int>answer(n+1,0);\n        vector<int>cnt(n+1,0);\n        for(int i=0;i<=n;i++){\n            cnt[i]=shortestPath(i,adj1,n+1,k);\n        }\n\n        vector<int>cnt2(m+1,0);\n        for(int i=0;i<=m;i++){\n            cnt2[i]=shortestPath(i,adj2,m+1,k-1);\n        }\n        int goldenNodeCnt=0;\n        for(int i=0;i<=m;i++){\n            goldenNodeCnt=max(goldenNodeCnt,cnt2[i]);\n        }\n\n        for(int i=0;i<=n;i++){\n            answer[i]=goldenNodeCnt+cnt[i];\n        }\n        return answer;\n    }\n};\n```
['Breadth-First Search', 'Shortest Path', 'C++']