23.06.02 Today’s Leetcode

2101. Detonate the Maximum Bombs (medium)

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        tree = defaultdict(set)
        def dst(point1, point2):
            return (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2
        
        n = len(bombs)
        for i in range(n):
            for j in range(n):
                if j == i:
                    continue
                if dst(bombs[i], bombs[j]) <= bombs[i][2] ** 2:
                    tree[i].add(j)
        # print(tree)
        
        visited = [0] * n
        def dfs(cur):
            if visited[cur]:
                return
            visited[cur] = 1
            for node in tree[cur]:
                dfs(node)
    
        res = 0
        for i in range(n):
            visited = [False] * n
            dfs(i)
            res = max(res, sum(visited))

        return res