Maximize the Number of Target Nodes After Connecting Trees II

Lowkey, this question does not seem toooooo hard.

Basically, for both graphs, we can iterate through all the nodes and colour each one red or blue such that no two neighbouring nodes share the same colour.

• then, realise that to find all the nodes that are target to a chosen node, we just need to count the number of nodes that share the same colour as it

Knowing this, we just need to:

• find the count of the dominant colour present on edges2, majorityColour2
• iterate through the nodes in edges1; at node i, calculate the count of nodes that share the same colour as it and place the values at ans[i]
  • add majorityColour2 to all the elements of ans

Finally, we can simply just return ans.

code

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        vector<vector<int>> adjacencyArray1 (edges1.size()+1);
        vector<vector<int>> adjacencyArray2 (edges2.size()+1);

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

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

        vector<int> colour1 (edges1.size()+1, 0);

        vector<int> colour2 (edges2.size()+1, 0);
        queue<int> q;
        q.push(0);
        colour2[0] = 1;
        int majorityColour2 = 1;

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int& adjacentNode : adjacencyArray2[node]) {
                if (colour2[adjacentNode] == 0) {
                    q.push(adjacentNode);
                    colour2[adjacentNode] = colour2[node] ^ 3;
                    if (colour2[adjacentNode] == 1) {
                        ++majorityColour2;
                    }
                }
            }
        }

        majorityColour2 = max(majorityColour2, (int)edges2.size()+1-majorityColour2);

        vector<int> ans ((int)edges1.size()+1, majorityColour2);
        q.push(0);
        colour1[0] = 1;

        int majorityColour1 = 1;
        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int& adjacentNode : adjacencyArray1[node]) {
                if (colour1[adjacentNode] == 0) {
                    q.push(adjacentNode);
                    colour1[adjacentNode] = colour1[node] ^ 3;
                    if (colour1[adjacentNode] == 1) {
                        ++majorityColour1;
                    }
                }
            }
        }

        for (int i = 0; i < edges1.size()+1; ++i) {
            if (colour1[i] == 1) {
                ans[i] += majorityColour1;
            } else {
                ans[i] += (int)edges1.size()+1 - majorityColour1;
            }
        }
        return ans;
    }
};

complexity

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

time taken

• 15 minutes and 20 seconds