diff options
author | Jack Sangdahl <[email protected]> | 2025-05-27 18:38:29 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-27 18:38:29 -0600 |
commit | b8408a05bc8c1d6fb74b4bcbb030caddcfb318e1 (patch) | |
tree | 9b77789343a4333909dd5c6414e008b396625f64 | |
parent | 74934eb304f3205b3eb61f4e970fc70e9b6383e2 (diff) | |
download | leetcode-b8408a05bc8c1d6fb74b4bcbb030caddcfb318e1.tar.gz leetcode-b8408a05bc8c1d6fb74b4bcbb030caddcfb318e1.zip |
3372. maximise the number of target nodes after connecting trees 1
-rw-r--r-- | maximise_num_target_node_tree1.py | 64 |
1 files changed, 64 insertions, 0 deletions
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, + ) + ) |