Python | BFS / DFS, start with every point | explanation
If the distance between bombs[i] and bombs[j] is smaller than or equal to the radius of bombs[i], then we can detonate bombs[j] with bombs[i]. This relationship
If the distance between `bombs[i]` and `bombs[j]` is smaller than or equal to the `radius` of `bombs[i]`, then we can detonate `bombs[j]` with `bombs[i]`. This relationship can be viewed as an edge `i -> j`.\n\nWe can enumerate all bomb pairs to construct a directed graph with these detonation relationships. And then we start with every bomb, use BFS / DFS to find how many bombs that we can reach.\n\nTime Complexity:\n* Construct Graph: `O(N ** 2)`\n* DFS / BFS (one time) is `O(N ** 2)` since there are at most `O(N ** 2)` edges in the constructed graph. We do BFS `N` times, so the worst complexity is `O(N ** 3)`.\n\n```python\nclass Solution:\n    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n        \n        N = len(bombs)\n        \n        # construct directed graph\n        G = defaultdict(list)\n        for i in range(N):\n            for j in range(N):\n                if i == j:\n                    continue\n                bi = bombs[i]\n                bj = bombs[j]\n                if (bi[0] - bj[0]) ** 2 + (bi[1] - bj[1]) ** 2 <= bi[2] ** 2:\n                    G[i].append(j)\n\n        # apply DFS with every bomb as start point\n        max_ans = 1\n        for start in range(N):\n            queue = [start]\n            visited = set([start])\n            this_ans = 0\n            while queue:\n                pos = queue.pop()\n                this_ans += 1\n                for neib in G[pos]:\n                    if neib not in visited:\n                        queue.append(neib)\n                        visited.add(neib)\n            max_ans = max(this_ans, max_ans)\n            if max_ans == N:\n                return N\n        return max_ans\n```\n\n
[]