# 2101. Detonate the Maximum Bombs
###### tags: `Leetcode` `Medium` `BFS`
Link: https://leetcode.com/problems/detonate-the-maximum-bombs/
## 思路
用bfs 先找到每个bomb引爆之后 它还能引爆哪些bomb 然后对每个bomb做bfs
不能用union find的原因是因为union find只用于无向图 而这题有向图（[解释](https://leetcode.com/problems/detonate-the-maximum-bombs/discuss/1623585/This-is-why-Union-Find-doesn't-work-for-this-problem-with-diagram)）
## Code

class Solution {
    public int maximumDetonation(int[][] bombs) {
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0; i<bombs.length; i++){
            List<Integer> temp = new ArrayList<>();
            for(int j=0; j<bombs.length; j++){
                long e1 = Math.abs(bombs[i][0]-bombs[j][0]);
                long e2 = Math.abs(bombs[i][1]-bombs[j][1]);
                long r = bombs[i][2];
                if(e1*e1+e2*e2<=r*r) temp.add(j);
            }
            graph.add(temp);
        }
        
        int max = 0;
        for(int i=0; i<bombs.length; i++){
            max = Math.max(max, bfs(graph, i));
        }
        return max;
    }
    private int bfs(List<List<Integer>> graph, int first){
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];
        q.add(first);
        visited[first] = true;
        int num = 0;
        while(!q.isEmpty()){
            int curr = q.poll();
            num++;
            for(int next:graph.get(curr)){
                if(!visited[next]){
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
        return num;
    }
}