3633. Maximize the Number of Target Nodes After Connecting Trees I
My accepted Python solution to LeetCode problem 3633, Maximize the Number of Target Nodes After Connecting Trees I, running in 2091ms.
- Difficulty: Medium
- Python
- Runtime 2091ms
- Memory 18.2MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 2091ms, memory 18.2MB, accepted 2025-12-31.
class Solution:
def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:
from collections import defaultdict, deque
def bfs(graph, start, maxd):
if maxd < 0:
return 0
vis = {start}
q = deque([(start, 0)])
cnt = 0
while q:
node, d = q.popleft()
if d <= maxd:
cnt += 1
for nei in graph[node]:
if nei not in vis:
vis.add(nei)
q.append((nei, d + 1))
return cnt
n, m = len(edges1) + 1, len(edges2) + 1
g1, g2 = defaultdict(list), defaultdict(list)
for u, v in edges1:
g1[u].append(v)
g1[v].append(u)
for u, v in edges2:
g2[u].append(v)
g2[v].append(u)
c1 = [bfs(g1, i, k) for i in range(n)]
mc2 = max(bfs(g2, i, k - 1) for i in range(m))
return [c + mc2 for c in c1]