Kosaraju's Algorithm + Topological Sort
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is an attempt to arrive at an O(n^2) solution by using the concept of Strongly Con
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is an attempt to arrive at an $$O(n^2)$$ solution by using the concept of Strongly Connected Components. This approach still runs at $$O(n^3)$$ time.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1) Creation of adjacency list and reversed adjacency list. This costs looping through the vertices twice, therefore this costs $$O(n^2)$$.\n\n2) Kosaraju\'s algorithm. This costs running through the adjacency list twice. The adjacency list can have $$n^2$$ items. Therefore, this costs $$O(n^2)$$.\n\n3) Topological sort in reversed order. We avoid double counting of bombs by using hashset on each node. We update the child hashset when the parent detonates the child. Updating a set with multiple items costs $$O(n)$$. The topological sort algorithm runs through the $$n^2$$ items. Therefore, the total is $$O(n^3)$$.\n\n# Complexity\n- Time complexity: $$O(n^3)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n        # // Adjacency List\n        b = [Bomb(x, y, r) for x, y, r in bombs]\n        adj = defaultdict(list)\n        r_adj = defaultdict(list)\n        for bomb1 in b:\n            for bomb2 in b:\n                if bomb1 == bomb2:\n                    continue\n                if bomb1.enclosed(bomb2):\n                    adj[bomb1].append(bomb2)\n                    r_adj[bomb2].append(bomb1)\n\n        # // Kosaraju\'s Algorithm for SCC\n        stack = []\n        visited = set()\n        def dfs1(node):\n            if node in visited:\n                return\n\n            visited.add(node)\n            for nei in adj[node]:\n                dfs1(nei)\n\n            stack.append(node)\n        \n        for bomb in b:\n            dfs1(bomb)\n\n        who = defaultdict(Bomb)\n        visited = set()\n        def dfs2(node, root):\n            if node in visited:\n                return\n            visited.add(node)\n            who[node] = root\n            for nei in r_adj[node]:\n                dfs2(nei, root)\n        \n        while stack:\n            curr = stack.pop()\n            if curr in visited:\n                continue\n            dfs2(curr, curr)\n\n        \n        # // Reversed Topological Sort\n        representatives = set(list(who.values()))\n        weights = {u: 0 for u in representatives}\n        indegree = {u: 0 for u in representatives}\n        new_adj = defaultdict(set)\n        for u in b:\n            for v in adj[u]:\n                if who[u] == who[v]:\n                    continue\n                if who[u] in new_adj[who[v]]:\n                    continue\n                new_adj[who[v]].add(who[u])\n                indegree[who[u]] += 1\n\n        for u in who:\n            weights[who[u]] += 1\n        \n        q = deque()\n        for u in indegree:\n            if indegree[u] == 0:\n                q.append(u)\n\n        res = {u: set([u]) for u in representatives}\n        visited = set()\n        while q:\n            for _ in range(len(q)):\n                node = q.popleft()\n                for child in new_adj[node]:\n                    if child in visited:\n                        continue\n                    \n                    # // Update set to avoid double counts\n                    res[child].update(res[node])\n                    \n                    indegree[child] -= 1\n                    if indegree[child] == 0:\n                        q.append(child)\n                        visited.add(child)\n        \n        # // Sum weights inside the set and take max\n        maxb = 0\n        for u in res:\n            curr = 0\n            for i in res[u]:\n                curr += weights[i]\n            maxb = max(maxb, curr)\n\n        return maxb\n        \n\nclass Bomb:\n    def __init__(self, x, y, r):\n        self.x = x\n        self.y = y\n        self.r = r\n\n    def enclosed(self, other):\n        return self.r ** 2 >= (self.x - other.x) ** 2 + (self.y - other.y) ** 2\n```
['Breadth-First Search', 'Topological Sort', 'Strongly Connected Component', 'Python3']