aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-27 18:38:29 -0600
committerJack Sangdahl <[email protected]>2025-05-27 18:38:29 -0600
commitb8408a05bc8c1d6fb74b4bcbb030caddcfb318e1 (patch)
tree9b77789343a4333909dd5c6414e008b396625f64
parent74934eb304f3205b3eb61f4e970fc70e9b6383e2 (diff)
downloadleetcode-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.py64
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,
+ )
+ )