Maximize the Number of Target Nodes After Connecting Trees I

This question is quite simple; I was just trying to optimise (disaster) for this question but could not come up with anything feasible.

However, you can simply just reduce this question down to:

find the number of elements you can BFS to with a distance of 'k' from each node in 'edges1' and add the MAXIMUM number of elements you can BFS to with a distance of `k-1` from any node in `edges2`

• in edges2, after BFS-ing from every node with a distance of k-1, find the maximum possible number of nodes that you can reach when starting on any node
  • let this value be maxGraph2
• then, create an ans vector, setting the value at each node to maxGraph2
• finally, we can just run BFS from every node with a distance of k and add it to ans[i]

code

class Solution {
public:
    int bfs (vector<vector<int>>& adjacencyVector, int startingNode, int distance) {
        if (distance < 0) return 0;
        queue<int> q;
        vector<int> seen (adjacencyVector.size());
        seen[startingNode] = 1;
        q.push(startingNode);
        int count = 1;

        while (distance > 0 && !q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                int node = q.front();
                q.pop();
                for (int& adjacentNode : adjacencyVector[node]) {
                    if (seen[adjacentNode] == 0) {
                        q.push(adjacentNode);
                        seen[adjacentNode] = 1;
                        ++count;
                    }
                }
            }
            --distance;
        }

        return count;
    }
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        vector<vector<int>> adjacencyVector1 (edges1.size()+1);
        vector<vector<int>> adjacencyVector2 (edges2.size()+1);

        for (vector<int>& edge : edges1) {
            adjacencyVector1[edge[0]].push_back(edge[1]);
            adjacencyVector1[edge[1]].push_back(edge[0]);
        }

        for (vector<int>& edge : edges2) {
            adjacencyVector2[edge[0]].push_back(edge[1]);
            adjacencyVector2[edge[1]].push_back(edge[0]);
        }

        int maxGraph2 = 0;
        for (int i = 0; i < edges2.size()+1; ++i) {
            maxGraph2 = max(maxGraph2, bfs(adjacencyVector2, i, k-1));
        }

        vector<int> ans (edges1.size()+1, maxGraph2);
        for (int i = 0; i < edges1.size()+1; ++i) {
            ans[i] += bfs(adjacencyVector1, i, k);
        }

        return ans;
    }
};

complexity

• Time: O(m^2 + n^2) where n denotes the size of edges1 and m denotes the size of edges2
• Space: O(m + n)