<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>

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        # idea: make a graph, where if bomb A has bomb B within its blast radius, A has an edge to B
        # (NOTE: this is not necessarily reflective, bomb B may or may not have a big enough blast
        # radius). Then, start at every node, every node visited has been "blown up", count the nodes
        # we can reach from the starting node, return the largest value. 

        # Detonate every bomb, we can't tell if that bomb will blow up 1 bombs or 100 bombs otherwise
        # If a bomb has been detonated before, we don't need to test it. Ex: Imagine bomb A was tested
        # and in the process detonated bomb B. Then testing bomb B will detonate all its "neighbors", and
        # so forth, but bomb A already calculated those so bomb A blows up at least the same amount
        # as bomb B can, maybe more. Detonating bomb B is then useless. When bomb C gets denotated 
        # (assume not previously deonated), then it might detonate bomb B and A, so they will have to
        # to be detonated again there to see what they get. So we can somewhat save time by not 
        # starting detonation at a bomb that has been detonated, but they might be detonated again 
        # through another starting bomb, time save is very situational

        graph = dict()

        for i in range(len(bombs)):
            for j in range(i+1, len(bombs)):
                bombA = bombs[i]
                bombB = bombs[j]

                distance = sqrt(( bombB[1] - bombA[1] )**2 + ( bombB[0] - bombA[0] )**2)

                # if bomb radius of A > distance to B
                if bombA[2] >= distance:
                    bombA_edges = graph.get(i, set())
                    bombA_edges.add(j)
                    graph[i] = bombA_edges

                if bombB[2] >= distance:
                    bombB_edges = graph.get(j, set())
                    bombB_edges.add(i)
                    graph[j] = bombB_edges
        
        detonated_prev = set()
        
        max_detonations = 0

        for bomb in range(len(bombs)):
            if bomb in detonated_prev:
                continue

            detonated_count = 0
            seen = set()
            queue = set()
            queue.add(bomb)

            while len(queue) > 0:
                current = queue.pop()

                if current in seen:
                    continue

                detonated_count += 1
                seen.add(current)

                for neighbor in graph.get(current, set()):
                    if neighbor in seen:
                        continue

                    queue.add(neighbor)
            

            max_detonations = max(max_detonations, detonated_count)

        print(graph)
        return max_detonations
        



567