<p>You are given a list of bombs. The <strong>range</strong> of a bomb is defined as the area where its effect can be felt. This area is in the shape of a <strong>circle</strong> with the center as the location of the bomb.</p>

<p>The bombs are represented by a <strong>0-indexed</strong> 2D integer array <code>bombs</code> where <code>bombs[i] = [x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub>]</code>. <code>x<sub>i</sub></code> and <code>y<sub>i</sub></code> denote the X-coordinate and Y-coordinate of the location of the <code>i<sup>th</sup></code> bomb, whereas <code>r<sub>i</sub></code> denotes the <strong>radius</strong> of its range.</p>

<p>You may choose to detonate a <strong>single</strong> bomb. When a bomb is detonated, it will detonate <strong>all bombs</strong> that lie in its range. These bombs will further detonate the bombs that lie in their ranges.</p>

<p>Given the list of <code>bombs</code>, return <em>the <strong>maximum</strong> number of bombs that can be detonated if you are allowed to detonate <strong>only one</strong> bomb</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-3.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> bombs = [[2,1,3],[6,1,4]]
<strong>Output:</strong> 2
<strong>Explanation:</strong>
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/06/desmos-eg-2.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> bombs = [[1,1,5],[10,10,5]]
<strong>Output:</strong> 1
<strong>Explanation:
</strong>Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/07/desmos-eg1.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
<strong>Output:</strong> 5
<strong>Explanation:</strong>
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= bombs.length&nbsp;&lt;= 100</code></li>
	<li><code>bombs[i].length == 3</code></li>
	<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

'''
How do I know if two bombs are intersecting? 

In an interval, put this question to later

Pseudocode
- For each circle, do a union-find with every other circle
- Then iterate through and find the largest "group"

O(n^2logn)

(69, 51, 7)
(65, 59, 3)

bomb1 denotating bomb2 does not mean bomb2 can detonate bomb1 because you're not comparing the ranges, you're comparing the centers...


Notes
- Union-Find won't work because bomb1 denotating bomb2 does not mean bomb2 can detonate bomb1
- DFS makes sense -> when you have dependencies that are linear...
'''

from collections import deque
class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        res = 0
        for i in range(len(bombs)):
            res = max(res, self.DFS(bombs, i))
            
        return res
    def DFS(self, bombs, src):
        queue = deque()
        queue.append(src)
        res = 0
        visited = set()
        visited.add(src)
        
        while queue:
            cur_bomb_idx = queue.popleft()
            res += 1
            
            for i in range(len(bombs)):
                if i not in visited and self.is_intersect(bombs[cur_bomb_idx], bombs[i]):
                    visited.add(i)
                    queue.append(i)
            
        return res
            
    def maximumDetonation2(self, bombs: List[List[int]]) -> int:
        parents = [i for i in range(len(bombs))]  

        for i in range(len(bombs)):
            for j in range(len(bombs)):
                if i != j and self.is_intersect(bombs[i], bombs[j]):
                    self.union_find(parents, i, j)
        
        cnts = defaultdict(int)
        res = 0
        for i in range(len(parents)):
            parent = self.find(parents, i)
            cnts[parent] += 1
            res = max(res, cnts[parent])
        
        return res
    
    def union_find(self, parents, x, y):
        parent_x = self.find(parents, x)
        parent_y = self.find(parents, y)
        
        parents[parent_x] = parent_y
        
    def find(self, parents, x):
        if parents[x] == x:
            return x
        
        parents[x] = self.find(parents, parents[x])
        return parents[x]
    
    def is_intersect(self, a, b):
        a_x, a_y, a_r = a[0], a[1], a[2]
        b_x, b_y, b_r = b[0], b[1], b[2]
        
        radius_squared = a_r**2
        center_dist = (b_y - a_y)**2 + (b_x - a_x)**2
        
        return radius_squared >= center_dist
2326