# 2101. Detonate the Maximum Bombs

• Time: $O(n^3)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public: int maximumDetonation(vector>& bombs) { const int n = bombs.size(); size_t ans = 0; vector> graph(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) continue; const long ri = bombs[i][2]; if (ri * ri >= squaredDist(bombs, i, j)) graph[i].push_back(j); } } for (int i = 0; i < n; ++i) { unordered_set seen{i}; dfs(graph, i, seen); ans = max(ans, seen.size()); } return ans; } private: void dfs(const vector>& graph, int u, unordered_set& seen) { for (const int v : graph[u]) { if (seen.count(v)) continue; seen.insert(v); dfs(graph, v, seen); } } long squaredDist(const vector>& bombs, int i, int j) { return static_cast(bombs[i][0] - bombs[j][0]) * (bombs[i][0] - bombs[j][0]) + static_cast(bombs[i][1] - bombs[j][1]) * (bombs[i][1] - bombs[j][1]); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public int maximumDetonation(int[][] bombs) { final int n = bombs.length; int ans = 0; List[] graph = new List[n]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) continue; final long ri = bombs[i][2]; if (ri * ri >= squaredDist(bombs, i, j)) graph[i].add(j); } } for (int i = 0; i < n; ++i) { Set seen = new HashSet<>(Arrays.asList(i)); dfs(graph, i, seen); ans = Math.max(ans, seen.size()); } return ans; } private void dfs(List[] graph, int u, Set seen) { for (final int v : graph[u]) { if (seen.contains(v)) continue; seen.add(v); dfs(graph, v, seen); } } private long squaredDist(int[][] bombs, int i, int j) { return (long) (bombs[i][0] - bombs[j][0]) * (bombs[i][0] - bombs[j][0]) + (long) (bombs[i][1] - bombs[j][1]) * (bombs[i][1] - bombs[j][1]); }; } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def maximumDetonation(self, bombs: List[List[int]]) -> int: n = len(bombs) ans = 0 graph = [[] for _ in range(n)] for i, (xi, yi, ri) in enumerate(bombs): for j, (xj, yj, rj) in enumerate(bombs): if i == j: continue if ri**2 >= (xi - xj)**2 + (yi - yj)**2: graph[i].append(j) def dfs(u: int, seen: Set[int]) -> None: for v in graph[u]: if v in seen: continue seen.add(v) dfs(v, seen) for i in range(n): seen = set([i]) dfs(i, seen) ans = max(ans, len(seen)) return ans