Python BFS/DFS and why union-find is not the solution.
Intuition\n Describe your first thoughts on how to solve this problem. \nMy initial intuition was union-find because it seems to find out the maximum RANK of th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy initial intuition was union-find because it seems to find out the maximum RANK of the largest group. After a few trial and error, I figured out that union-find is only for undirected graph. So, I decided to solve this problem with typical BFS, DFS, DFS-Recursive approach.  \n\n[Example]\nthere are three points\npoint 1 is located at x=2 with radius 5\npoint 2 is located at x=5 with radius 1\npoint 3 is located at x=10 with radius 6\n\nunion-find approach will build those three points as a graph. (max rank = 3)\nbut, in this scenario, the max value is 2 because the point 2 cannot detonate any bomb.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n0. Building adjacency list\n1. BFS with deque\n2. DFS with stack\n3. DFS with recursion\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(V + E)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(V)\n# Code\n```\nclass Solution:\n    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n\n        def is_connected(a,b):\n            x1, y1, r1 = bombs[a]\n            x2, y2, r2 = bombs[b]\n            dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)\n            return dist <= r1\n\n\n        conn = collections.defaultdict(list)\n        for i in range(len(bombs)):\n            for j in range(len(bombs)):\n                if i != j:\n                    if is_connected(i,j):\n                        conn[i].append(j)\n\n        # 1. BFS\n        # q = collections.deque()\n        # maxCount = float(\'-inf\')\n\n        # for node in range(len(bombs)):\n        #     if conn[node]:\n        #         q.append(node)\n        #         visited = set()\n        #         visited.add(node)\n        #         count = 0\n        #         while q:\n        #             curr = q.popleft()\n        #             count+=1\n        #             maxCount = max(maxCount, count)\n        #             for child in conn[curr]:\n        #                 if child not in visited:\n        #                     visited.add(child)\n        #                     q.append(child)\n\n        # return maxCount if maxCount != float(\'-inf\') else 1\n\n\n        # 2. DFS\n\n        # stack = []\n        # maxCount = float(\'-inf\')\n\n        # for node in range(len(bombs)):\n        #     if conn[node]:\n        #         visited = set()\n        #         stack.append(node)\n        #         visited.add(node)\n        #         count = 0\n        #         while stack:\n\n        #             curr = stack.pop()\n        #             count+=1\n        #             maxCount = max(maxCount, count)\n\n        #             for child in conn[curr]:\n        #                 if child not in visited:\n        #                     visited.add(child)\n        #                     stack.append(child)\n        # return maxCount if maxCount != float(\'-inf\') else 1\n\n\n        # 3. DFS recursive                \n                    \n        def dfs(node):\n\n            if node in visited:\n                return 0\n\n            visited.add(node)\n            \n            ans = 1\n\n            if node in conn:\n                for child in conn[node]:\n                    if child in visited:\n                        continue\n                    ans += dfs(child)\n            \n            return ans \n\n        maxCount = 1\n        for node in conn:\n            visited = set()\n            maxCount = max(maxCount, dfs(node))\n        return maxCount\n```
['Python3']