From b8408a05bc8c1d6fb74b4bcbb030caddcfb318e1 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Tue, 27 May 2025 18:38:29 -0600 Subject: 3372. maximise the number of target nodes after connecting trees 1 --- maximise_num_target_node_tree1.py | 64 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) create mode 100644 maximise_num_target_node_tree1.py diff --git a/maximise_num_target_node_tree1.py b/maximise_num_target_node_tree1.py new file mode 100644 index 0000000..d811536 --- /dev/null +++ b/maximise_num_target_node_tree1.py @@ -0,0 +1,64 @@ +# 3372. Maximize the Number of Target Nodes After Connecting Trees I + +""" +there exists two undirected trees with 'n' and 'm' nodes with distinct labels +in ranges '[0, n - 1]' respectively. you are given two 2d integer arrays +'edges1' and 'edges2' of length 'n - 1' and 'm - 1' where 'edges[i] = [ai, +bi]' indicates that there is an edge between nodes 'ai' and 'bi' in the first +tree and 'edges2[i] = [ui, vi]' indicates that there is an edge between nodes +'ui' and 'vi' in the second tree. you are also given an integer 'k'. return +an array of 'n' integers 'answer' where 'answer[i]' is the maximum possible +number of nodes target to node 'i' of the first tree if you have to connect +one node from the first tree to another node in the second tree. +""" + + +class Solution(object): + def maxTargetNodes(self, edges1, edges2, k): + """ + :type edges1: List[List[int]] + :type edges2: List[List[int]] + :type k: int + :rtype: List[int] + """ + n, m, x = len(edges1) + 1, len(edges2) + 1, 0 + if k == 0: + return [1] * n + + def dfs(node, level, parent, cnt=1): + if level < k: + for i in graph[node]: + if i == parent: + continue + cnt += dfs(i, level + 1, node) + return cnt + + graph = [[] for _ in range(m)] + for u, v in edges2: + graph[u].append(v) + graph[v].append(u) + for i in range(m): + x = max(x, dfs(i, 1, -1)) + graph = [[] for _ in range(n)] + for u, v in edges1: + graph[u].append(v) + graph[v].append(u) + return [dfs(i, 0, -1) + x for i in range(n)] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.maxTargetNodes( + edges1=[[0, 1], [0, 2], [2, 3], [2, 4]], + edges2=[[0, 1], [0, 2], [0, 3], [2, 7], [1, 4], [4, 5], [4, 6]], + k=2, + ) + ) + print( + obj.maxTargetNodes( + edges1=[[0, 1], [0, 2], [0, 3], [0, 4]], + edges2=[[0, 1], [1, 2], [2, 3]], + k=1, + ) + ) -- cgit v1.2.3