[Leetcode] 3373. Maximize the Number of Target Nodes After Connecting Trees II

https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-ii/description/?envType=daily-question&envId=2025-05-29

initial

VERY IMPT
If u have n edges, tree MUST have n+1 nodes by defintition

So when initialising graph, u must say len(edges)+1!!

I can see the pattern

first example
        # even=0,3,4
        # odd=1,2

        # even=0,7,1,5,6
        # odd=2,3,4
        
second example
        # even=0
        # odd=1,2,3,4

        # even=0,2
        # odd=1,3

so we can take any bigger values of even and off nodes for the second tree and add them to our first tree node. First tree nodes have to be dfsed to transform into a bipartite graph of even and odd nodes.

If the iterating node belongs to an even subset like for first example, if we are at node 0, it belongs to the even subset. So We should add the number of this even subset size (3) + max(even2,odd2) of second graph so it gives us 3+5=8

v impt to get this pattern first which i got

sol

Also v impt that integers in py are immutable. We should not pass even1,odd1 to our dfs parameters but instead use a list object of count1 which 0th index will store even nodes and 1st index stores odd number of nodes.

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
        n1, n2 = len(edges1) + 1, len(edges2) + 1
        graph1 = [[] for _ in range(n1)]
        graph2 = [[] for _ in range(n2)]
        for start, end in edges1:
            graph1[start].append(end)
            graph1[end].append(start)
        for start, end in edges2:
            graph2[start].append(end)
            graph2[end].append(start)

        # Use lists to hold counts because lists are mutable
        count1 = [0, 0]  # count1[0] = even, count1[1] = odd
        count2 = [0, 0]

        answer1=[0 for _ in range(n1)]
        answer2=[0 for _ in range(n2)]

        def dfs(graph, node, depth, count, visited,answer):
            if visited[node]:
                return
            visited[node] = True
            if depth % 2 == 0:
                count[0] += 1
            else:
                answer[node]=1
                count[1] += 1
            for neigh in graph[node]:
                if not visited[neigh]:
                    dfs(graph, neigh, depth + 1, count, visited,answer)

        visited1 = [False] * n1
        visited2 = [False] * n2
        dfs(graph1, 0, 0, count1, visited1,answer1)
        dfs(graph2, 0, 0, count2, visited2,answer2)

        even1, odd1 = count1
        even2, odd2 = count2

        ans = []
        for i in range(n1):
            if answer1[i] == 0:
                ans.append(even1 + max(even2, odd2))
            else:
                ans.append(odd1 + max(even2, odd2))
        return ans

complexity

Time Complexity: O(n1 + n2)
Breakdown:

Graph construction: O(n1 + n2) - iterating through all edges in both graphs
DFS traversals: O(n1) + O(n2) - each node is visited exactly once in each graph
Result construction: O(n1) - iterating through nodes in graph1 to build the answer

Total: O(n1 + n2)

Space Complexity: O(n1 + n2)
Breakdown:

Graph storage: O(n1 + n2) - adjacency lists store all edges
Arrays: O(n1 + n2) - visited arrays, answer arrays, etc.
DFS call stack: O(max(n1, n2)) - in worst case (linear tree), recursion depth equals number of nodes

Total: O(n1 + n2)