[Python] Simple dfs, explained
In fact, this is graph proglem, starting with bomb, we need to traverse all bombs we can detonate and so on. Problem constraints allow us to just use bruteforce
In fact, this is graph proglem, starting with bomb, we need to traverse all bombs we can detonate and so on. Problem constraints allow us to just use bruteforce.\n\n#### Complexity\nTime complexity is `O(n^3)`, because we start from `n` bombs and we can have upto `O(n^2)` edges.\n\n#### Code\n```python\nclass Solution:\n    def maximumDetonation(self, B):\n        n, ans, G = len(B), 0, defaultdict(list)\n        \n        for i in range(n):\n            for j in range(n):\n                if i == j: continue\n                if B[i][2]**2 >= (B[i][0] - B[j][0])**2 + (B[i][1] - B[j][1])**2:\n                    G[i] += [j]\n        \n        \n        def dfs(node, visited):\n            for child in G[node]:\n                if child not in visited:\n                    visited.add(child)\n                    dfs(child, visited)\n\n        for i in range(n):\n            visited = set([i])\n            dfs(i, visited)\n            ans = max(ans, len(visited))\n                          \n        return ans\n```\n\n#### Remark\nThere is also `O(n^2)` solution: let us keep for each node set of nodes we can reach from this node: than we can recalculate it with usual dfs.\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Depth-First Search']