Detonate the Maximum Bombs solution and explanation

from collections import deque

def can_detonate(bomb1, bomb2):
    x1, y1, r1 = bomb1
    x2, y2, _ = bomb2
    return (x1 - x2)**2 + (y1 - y2)**2 <= r1**2


def maximum_detonation(bombs):
    n = len(bombs)
    graph = [[] for _ in range(n)]

    # Build graph
    for i in range(n):
        for j in range(n):
            if i != j and can_detonate(bombs[i], bombs[j]):
                graph[i].append(j)

    def bfs(start):
        visited = [False] * n
        queue = deque([start])
        visited[start] = True
        count = 0

        while queue:
            current = queue.popleft()
            count += 1
            for neighbor in graph[current]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

        return count

    max_detonated = 0
    for i in range(n):
        max_detonated = max(max_detonated, bfs(i))

    return max_detonated

import java.util.*;

class Solution {
    private boolean canDetonate(int[] bomb1, int[] bomb2) {
        long x1 = bomb1[0], y1 = bomb1[1], r1 = bomb1[2];
        long x2 = bomb2[0], y2 = bomb2[1];
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1;
    }

    public int maximumDetonation(int[][] bombs) {
        int n = bombs.length;
        List<Integer>[] graph = new ArrayList[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 && canDetonate(bombs[i], bombs[j])) {
                    graph[i].add(j);
                }
            }
        }

        int maxDetonated = 0;
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            visited[i] = true;
            int count = 0;

            while (!queue.isEmpty()) {
                int current = queue.poll();
                count++;
                for (int neighbor : graph[current]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
            maxDetonated = Math.max(maxDetonated, count);
        }

        return maxDetonated;
    }
}

#include <vector>
#include <cmath>
using namespace std;

bool canDetonate(const vector<int>& bomb1, const vector<int>& bomb2) {
    long long x1 = bomb1[0], y1 = bomb1[1], r1 = bomb1[2];
    long long x2 = bomb2[0], y2 = bomb2[1];
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1;
}

void dfs(const vector<vector<int>>& graph, vector<bool>& visited, int index, int& count) {
    visited[index] = true;
    count++;
    for (int neighbor : graph[index]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor, count);
        }
    }
}

int maximumDetonation(vector<vector<int>>& bombs) {
    int n = bombs.size();
    vector<vector<int>> graph(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && canDetonate(bombs[i], bombs[j])) {
                graph[i].push_back(j);
            }
        }
    }

    int maxDetonated = 0;
    for (int i = 0; i < n; i++) {
        vector<bool> visited(n, false);
        int count = 0;
        dfs(graph, visited, i, count);
        maxDetonated = max(maxDetonated, count);
    }

    return maxDetonated;
}

function canDetonate(bomb1, bomb2) {
    let [x1, y1, r1] = bomb1;
    let [x2, y2] = bomb2;
    return (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r1 ** 2;
}

function dfs(graph, visited, index) {
    visited[index] = true;
    let count = 1;
    for (let neighbor of graph[index]) {
        if (!visited[neighbor]) {
            count += dfs(graph, visited, neighbor);
        }
    }
    return count;
}

function maximumDetonation(bombs) {
    let n = bombs.length;
    let graph = Array.from({ length: n }, () => []);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j && canDetonate(bombs[i], bombs[j])) {
                graph[i].push(j);
            }
        }
    }

    let maxDetonated = 0;
    for (let i = 0; i < n; i++) {
        let visited = Array(n).fill(false);
        let detonatedCount = dfs(graph, visited, i);
        maxDetonated = Math.max(maxDetonated, detonatedCount);
    }

    return maxDetonated;
}

function maximumDetonation(bombs: number[][]): number {
    const n = bombs.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 0; i < n - 1; ++i) {
        const [x1, y1, r1] = bombs[i];
        for (let j = i + 1; j < n; ++j) {
            const [x2, y2, r2] = bombs[j];
            const d = Math.hypot(x1 - x2, y1 - y2);
            if (d <= r1) {
                g[i].push(j);
            }
            if (d <= r2) {
                g[j].push(i);
            }
        }
    }
    let ans = 0;
    for (let k = 0; k < n; ++k) {
        const vis: Set<number> = new Set([k]);
        const q: number[] = [k];
        for (const i of q) {
            for (const j of g[i]) {
                if (!vis.has(j)) {
                    vis.add(j);
                    q.push(j);
                }
            }
        }
        if (vis.size === n) {
            return n;
        }
        ans = Math.max(ans, vis.size);
    }
    return ans;
}

func maximumDetonation(bombs [][]int) (ans int) {
	n := len(bombs)
	g := make([][]int, n)
	for i, p1 := range bombs[:n-1] {
		for j := i + 1; j < n; j++ {
			p2 := bombs[j]
			dist := math.Hypot(float64(p1[0]-p2[0]), float64(p1[1]-p2[1]))
			if dist <= float64(p1[2]) {
				g[i] = append(g[i], j)
			}
			if dist <= float64(p2[2]) {
				g[j] = append(g[j], i)
			}
		}
	}
	for k := 0; k < n; k++ {
		q := []int{k}
		vis := make([]bool, n)
		vis[k] = true
		cnt := 0
		for len(q) > 0 {
			i := q[0]
			q = q[1:]
			cnt++
			for _, j := range g[i] {
				if !vis[j] {
					vis[j] = true
					q = append(q, j)
				}
			}
		}
		if cnt == n {
			return n
		}
		ans = max(ans, cnt)
	}
	return
}