Optimal DFS (Detailed Explanation) | 27ms
Explanation\nThis problem can be approached from the perspective of the bombs being associated with each other in a directed manner (i.e. for a pair of bombs i 
# Explanation\nThis problem can be approached from the perspective of the bombs being associated with each other in a directed manner (i.e. for a pair of bombs `i` and `j`, there can be a case where bomb `i` can blow up bomb `j`, but bomb `j` cannot blow up bomb `i`, and vice versa). Because of this, the bombs have a 1-way association with each other, which we can then deduce means that the bombs can be represented with a directed graph. We must be careful to realize that it is not guaranteed to be acyclic, as there can also be the case where bomb `i` can blow up bomb `j`, and bomb `j` can also blow up bomb `i`, etc. \n\nSo now we understand how we can represent the problem using a data structure we are familiar with. In my case, we will use an adjancency list where for a bomb `i` we know the neighboring bombs that we can reach (calculated using Squared Euclidean distance compared with blast radius of bomb `i`). \n\nWith our intuition for how the bombs are represented, we can identify that we can calculate the total bombs that will be detonated if we start at any given bomb `i` by performing a DFS, starting at `i`. This is because if we can reach a bomb `j` starting at bomb `i` in our graph, it means that the explosion from bomb `i` will set off bomb `j`. \n\nOf course because the graph is not guaranteed to be acyclic, we need to be sure to avoiding trapping ourselves in a loop (i.e. visiting the same bomb twice). The traditional method for doing so is to keep a `visited` set, and check whether or not we have already visited that bomb using that set before proceeding. Now, one pitfall with our `visited` set is that theoretically we will have to reset it after each iteration, because there is a case where we would have marked a chain of bombs as visited from a non-maximal starting point, meaning that when we attempt to visit that chain of bombs from the maximal starting point, we will not be able to, making our code incorrect for that case. To avoid this, most implementations appear to just reset the `visited` set for each starting bomb, however this can potentially be expensive. Therefore, my way for getting around this is to keep a visited set of type `short`, where the store number represents the starting bomb for which that bomb in `vis` has been visited already. \n\nThis essentially means that we can keep one set throughout the whole DFS, updating the set as we go with the starting bomb\'s index, and checking whether or not the current DFS we are performing originated at that starting index, and if it did not, then we know we have not visited that bomb in this current iteration and we may proceed with our exploration. Doing this is a key optimization, as we avoid having to recreate a set each time we want to start at a bomb. It also means we can skip starting at a bomb that has already been visited before, because we know that if we have visited it in the past, we have already found the maximum bombs that it can detonate from that point. \n\n# Code\n```C++ []\nclass Solution {\npublic:\n    typedef long long LL;\n    vector<vector<short>> adj;\n    vector<short> vis;\n\n    // Check if a bomb is in the blast radius of another bomb\n    bool inRange(const LL & x1, const LL & x2, const LL & y1, const LL & y2, const LL & r) {\n        return ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) <= (r * r);\n    }\n\n    // Build our graph\n    void buildGraph(vector<vector<int>> & bombs) {\n        const int LENGTH = bombs.size();\n        for (short i = 0; i < LENGTH; i++) {\n            for (short j = i + 1; j < LENGTH; j++) {\n                if (inRange(bombs[i][0], bombs[j][0], bombs[i][1], bombs[j][1], bombs[i][2])) adj[i].push_back(j);\n                if (inRange(bombs[i][0], bombs[j][0], bombs[i][1], bombs[j][1], bombs[j][2])) adj[j].push_back(i);\n            }\n        }\n    }\n\n    // Our simple DFS\n    // Only complexity is the reuse of the visited set\n    int countBombs(vector<vector<int>> & bombs, int bomb, int start) {\n        if (vis[bomb] == start) return 0;\n        vis[bomb] = start;\n        int count = 1;\n        for (const auto & i : adj[bomb]) count += countBombs(bombs, i, start);\n        return count;\n    }\n\n    int maximumDetonation(vector<vector<int>>& bombs) {\n        const int LENGTH = bombs.size();\n        adj.resize(LENGTH);\n        vis.resize(LENGTH, -1);\n        buildGraph(bombs);\n\n        int maxBombs = 0;\n        for (short i = 0; i < LENGTH; i++) if (vis[i] == -1) maxBombs = max(maxBombs, countBombs(bombs, i, i));\n        return maxBombs;\n    }\n};\n```\n
['Depth-First Search', 'C++']