C++ DFS/BFS solutions  with detonating bomb process beating 90.22%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe crucial part is to create the directed graph, i.e. the adjacent list. The bombs are
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe crucial part is to create the directed graph, i.e. the adjacent list. The bombs are the the vertice. If bomb[j] is within the bomb range of bomb[i], there is a directed edge from bomb[i] to bomb[j]. Then either of DFS or BFS can be applied for solving this problem.\n\nAccording the radius of bomb range, sort the bombs in descending order. Then create adjacent list according to Euclidean distance fomula:\n$$\nd^2((x, y),(x_j, y_j))=(x-x_j)^2+(y-y_j)^2\\leq r^2  \\qquad(1)\n$$\nwhere $(x, y,r)$ is the info for the  detonating bomb[i] and the bomb[j] with coordinates $(x_j, y_j)$ lies within the bomb[i] range. The computation for the inequality needs to use long long int to prevent overflow! But there are many cases that the bomb is closed to the detonating bomb.\n\nSo, we used firstly the easy computing to test whether\n$$\n|x-x_j|+|y-y_j|\\leq r \\qquad(2)\n$$\nif the inequality  (2) that\'s fine add j to adj[i], if not then try the inequality (1) for Euclidean distance fomula. It is clear if the inequality (2) is satisfied, then the inequalty (1) is valid since the triangle inequality.\n[DFS& BFS solves Leetcode 934 shortest bridge with English subtitles, please turn on if necessary]\n[https://youtu.be/9Lx7yr-tmfI](https://youtu.be/9Lx7yr-tmfI)\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTest case:\n```\n[[647,457,91],[483,716,37],[426,119,35],[355,588,40],[850,874,49],[232,568,46],[886,1,30],[54,377,3],[933,986,50],[305,790,49],[372,961,67],[671,314,58],[577,221,29],[380,147,91],[600,535,1],[806,329,64],[536,753,18],[906,88,23],[436,783,82],[652,674,45],[449,668,20],[419,13,66],[853,767,60],[169,288,33],[871,608,66],[337,445,35],[388,623,39],[723,503,81],[14,19,19],[98,648,72],[147,565,93],[655,434,1],[407,663,22],[805,947,83],[942,160,70],[959,496,93],[30,988,53],[187,849,60],[980,483,41],[663,150,76],[268,39,50],[513,522,75],[61,450,90],[115,231,12],[346,304,74],[385,540,23],[905,178,19],[336,896,81],[751,811,94],[527,783,78],[635,965,19],[334,290,39],[748,460,77],[414,134,22],[955,485,29],[925,787,43],[243,771,75],[675,223,29],[788,618,82],[462,544,30],[999,259,50],[210,146,12],[789,442,70],[286,36,55],[451,953,6],[719,914,14],[664,452,14],[933,637,29],[206,926,16],[100,422,98],[97,333,4],[505,631,26],[908,287,65],[907,316,86],[949,185,16],[639,735,62],[401,739,18],[605,926,21],[25,391,69],[80,24,9],[435,874,92],[940,381,18],[260,740,87],[727,515,17],[361,152,16],[512,470,67],[189,27,27],[517,439,94],[159,543,76],[373,698,38],[781,836,97],[584,190,23],[383,367,86],[825,141,63],[117,926,85],[169,588,60],[56,981,100],[294,716,100],[781,370,89],[373,44,78]]\n```\nSort the bombs! Create the adjacent list\n```\nn=100\n56,981,100\n294,716,100\n100,422,98\n781,836,97\n751,811,94\n517,439,94\n147,565,93\n959,496,93\n435,874,92\n647,457,91\n380,147,91\n61,450,90\n781,370,89\n260,740,87\n383,367,86\n907,316,86\n117,926,85\n805,947,83\n436,783,82\n788,618,82\n336,896,81\n723,503,81\n527,783,78\n373,44,78\n748,460,77\n159,543,76\n663,150,76\n243,771,75\n513,522,75\n346,304,74\n98,648,72\n789,442,70\n942,160,70\n25,391,69\n372,961,67\n512,470,67\n871,608,66\n419,13,66\n908,287,65\n806,329,64\n825,141,63\n639,735,62\n187,849,60\n853,767,60\n169,588,60\n671,314,58\n286,36,55\n30,988,53\n933,986,50\n999,259,50\n268,39,50\n850,874,49\n305,790,49\n232,568,46\n652,674,45\n925,787,43\n980,483,41\n355,588,40\n388,623,39\n334,290,39\n373,698,38\n483,716,37\n337,445,35\n426,119,35\n169,288,33\n462,544,30\n886,1,30\n933,637,29\n955,485,29\n675,223,29\n577,221,29\n189,27,27\n505,631,26\n385,540,23\n584,190,23\n906,88,23\n407,663,22\n414,134,22\n605,926,21\n449,668,20\n635,965,19\n905,178,19\n14,19,19\n536,753,18\n401,739,18\n940,381,18\n727,515,17\n206,926,16\n949,185,16\n361,152,16\n719,914,14\n664,452,14\n115,231,12\n210,146,12\n80,24,9\n451,953,6\n97,333,4\n54,377,3\n600,535,1\n655,434,1\n=======\nadj lists:\n0:[16,47]\n1:[13,27,52,60]\n2:[11,33,96,97]\n3:[4,51]\n4:[3]\n5:[28,35]\n6:[25,44,53]\n7:[56,68]\n8:[18,95]\n9:[21,91,99]\n10:[63,77,89]\n11:[2,33,97]\n12:[31,39]\n13:[1,27,52]\n14:[29]\n15:[38,85]\n16:[0]\n18:[61,84]\n20:[34]\n21:[24,86,91]\n22:[83]\n23:[37]\n24:[21,31,86]\n25:[6,44]\n26:[69]\n27:[13,52]\n28:[35,65]\n29:[14,59]\n31:[24]\n32:[81,88]\n33:[97]\n35:[5,28]\n37:[23]\n38:[15]\n39:[12]\n44:[6,25]\n46:[50]\n47:[0]\n50:[46]\n56:[7,68]\n59:[29]\n63:[77]\n68:[7,56]\n77:[63]\n86:[21]\nans=7\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code with Explanation in Comments\nIf the sorting process is not used, the elapsed time is 90 ms and beats 90.22%.  With sorting, the elapsed time is 106 ms and beats 81.1%\n```\nclass Solution {\npublic:\n    int n;\n    int MaxBomb = 1;\n    vector<vector<int>> adj;\n\n    // Print the information of bombs\n    void print(vector<vector<int>>& bombs){\n        cout << "n=" << n << endl;\n        for(vector<int> b : bombs)\n            cout << b[0] << "," << b[1] << "," << b[2] << endl;\n    }\n\n    // Print the adjacent list information\n    void print_adj(){\n        cout << "=======\\nadj lists:\\n";\n        for(int i=0; i<n; i++){\n            cout << i << ":[";\n            for(int j=0; j<adj[i].size(); j++)\n                cout << adj[i][j] << ",";\n            cout << "]" << endl;\n        }\n    }\n\n    // Create the adjacent list\n    void create_adj(vector<vector<int>>& bombs){\n        for(int i=0; i<n; i++){\n            long long r = bombs[i][2], x = bombs[i][0], y = bombs[i][1];\n            for(int j=0; j<n; j++){\n                if(i != j){\n                    double xd = bombs[j][0] - x, yd = bombs[j][1] - y;\n                    if (abs(xd) + abs(yd) <= r) \n// If the distance is less than or equal to the radius, it might be very close to bomb[i]\n                        \n                        adj[i].push_back(j);\n                    else if (r*r >= xd*xd + yd*yd) \n// If the distance satisfies condition (1)\n                        adj[i].push_back(j);\n                }\n            }\n        }\n    }\n\n    vector<bool> detonated;\n\n    // Use Depth-First Search (DFS) recursively to calculate the number of bombs in the detonation range\n    void dfs(int i){\n        MaxBomb++;\n        detonated[i] = 1;\n        for(int j : adj[i]){\n            if(!detonated[j])\n                dfs(j);\n        }\n    }\n\n    int maximumDetonation(vector<vector<int>>& bombs) {\n        n = bombs.size();\n\n        // Sort the bombs in descending order based on the radius\n        sort(bombs.begin(), bombs.end(),\n        [](vector<int>& a, vector<int>& b ){\n            if(a[2] != b[2]) return a[2] > b[2];\n            return a[1] > b[1];\n        });\n\n        // Print the sorted bombs information\n        print(bombs);\n\n        adj.resize(n);\n        create_adj(bombs); // Create the adjacent list\n        print_adj(); // Print the adjacent list information\n\n        int ans = 0;\n        detonated.assign(n, 0);\n        for(int i = 0; i < n; i++){\n            if(!detonated[i]){\n                MaxBomb = 0;\n                dfs(i); // Call the DFS function to calculate the number of bombs in the detonation range\n                ans = max(ans, MaxBomb);\n            }\n            detonated.assign(n, 0);\n        }\n        cout << ans << endl;\n        return ans;\n    }\n};\n\n```\n# BFS can work too. Just replace dfs by bfs\n```\nvoid bfs(int i) {\n        queue<int> q;\n        q.push(i);\n        detonated[i] = 1;     \n        while (!q.empty()) {\n            int j = q.front();\n            q.pop();\n            MaxBomb++;        \n            for (int k : adj[j]) {\n                if (!detonated[k]) {\n                    q.push(k);\n                    detonated[k] = 1;\n                }\n            }\n        }\n    }\n```
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Geometry', 'C++']