C# | BFS | Detailed Explanation + Dry Run | Runtime Beats 87.47%
Intuition\nWhile reading the problem we get to understand that this is a sort of problem where a relationship needs to be established between bombs so that when
# Intuition\nWhile reading the problem we get to understand that this is a sort of problem where a relationship needs to be established between bombs so that when one explodes the other one does too. This becomes more clearer by the fact that the range is involved while deciding that. So with this information it becomes clear that it is a graph problem. Most of the graph problems revolve around 4 algorithms, DFS, BFS, Union Find and Topological Sort. Also one problem can be solved by more than one of these algorithms. Since we need to detonate maximum number of bombs by detonating a single bomb so at any given time all the children of a node are coming into the picture and hence BFS is the algorithm we will go with.\n\n# Approach\n\n**Example used - bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]**\n\n**Adjacency List Creation**\n\nOur solution starts by building the Adjacency List of the form in the image. This kind of structure can be used to represent both a directed and an undirected graph, the difference being that in undirected we will be adding two edges for each relationship, one for each node involved whereas in directed just one edge is added. In our case we will be using a directed graph since bomb 1 being in the range of bomb 2 does not mean it is true the other way around as the ranges differ for both of them even though the distance remains same.\nWe will be using the mathematical formula to calculate distance between any two bombs. If the range of the first bomb is greater than the calculated distance, we can assume that bomb 2 will detonate on the detonation of bomb 1 and hence there a directed edge from bomb 1 to bomb 2.\nOnce our Adjacency list is ready we need a way to find a way to detonate maximum bombs. For this we will be using the breadth first search algorithm to iterate over all nodes in the graph, then run the BFS for each of them since we don\'t know which bomb will detonate all the bombs. We also maintain the \'maxBombsDetonated\' state so that at any point if we detonate all bombs we don\'t need to iterate further and can exit then and there.\n\n![image.png](https://assets.leetcode.com/users/images/844c794c-7c05-4657-b355-f313133fb705_1689405355.7905874.png)\n\n\n**How BFS works**\n\nBreadth First Search is an algorithm to traverse the nodes of a graph in a breadth wise manner, what it means is instead of going in one direction straight like in DFS, we want to iterate over the current node as well as over all its children before moving onto a new node and its children thereafter, so in this manner we go level by level instead of in one direction depth wise. For BFS algorithm we use Queue data structure since it helps to preserve the order of insertion.\nThe exist condition for this is generally the queue count becoming zero as no more nodes are left to process. Also another important point is that we need to maintain a \'visited\' set inorder to not detonate a bomb again which has already been detonated since there could be a case in which we come back to the node from which we started via some other intermediate node.\nIn the below image I have shown a dry run for the example.\nHere since the first iteration with i = 0 itself detonates all 5 bombs we don\'t to traverse further and the code exists.\n\n![image.png](https://assets.leetcode.com/users/images/84407e38-69a9-42cc-9741-d5dc55121406_1689406682.9492385.png)\n\n# **If you found my solution and explanation helpful, please consider upvoting it. Your upvote will help rank it higher among other solutions, making it easier for people seeking assistance to find. Feel free to ask any follow-up questions in the comment section. Thank you for reading!**\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nInitializing the adjacency list: O(n)\n\nThe code initializes the adjacency list by creating a new list for each vertex. This takes O(n) time, where n is the number of bombs.\nConstructing the adjacency list: O(n^2)\n\nThe code constructs the adjacency list by checking the distance between each pair of bombs and adding an edge if they are adjacent. This involves nested loops, where the outer loop runs n times and the inner loop also runs n times. Therefore, this step takes O(n^2) time.\nBFS traversal: O(n + m)\n\nThe code performs a BFS traversal on the adjacency list. The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. In this case, the number of vertices is n, and the number of edges is the sum of the sizes of all lists in the adjacency list, which can be denoted as m. Therefore, the BFS traversal takes O(n + m) time.\nMain loop: O(n * (n + m))\n\nThe code iterates over each vertex and performs a BFS traversal on it. Since the BFS traversal takes O(n + m) time, and this is done for each of the n vertices, the overall time complexity of the main loop is O(n * (n + m)).\nOverall, the time complexity of the given code is O(n^2 + n + m), which can be simplified to O(n^2 + m) in the worst case.\n# Code\n```\npublic class Solution {\n    List<int>[] adjacencyList;\n    public int MaximumDetonation(int[][] bombs) \n    {\n        int n = bombs.Length;\n        adjacencyList = new List<int>[n];\n        int maxBombsDetonated = 0;\n\n        for(int i = 0 ; i < n ; i++)\n        {\n            adjacencyList[i] = new List<int>();\n        }\n\n        for(int i = 0 ; i < n ; i++)\n        {\n            for(int j = 0 ; j < n ; j++)\n            {\n                if(i != j)\n                {\n                    double dist = Math.Sqrt(Math.Pow((bombs[i][0]-bombs[j][0]),2) + Math.Pow((bombs[i][1] - bombs[j][1]),2));\n                    if(bombs[i][2] >= dist)\n                    {\n                        // bombs are adjacent if the second bomb lies in the range of first, drawing an edge from first to second\n                        adjacencyList[i].Add(j);\n                    }\n                }\n            }\n        }\n\n        for(int i = 0 ; i < n ; i++)\n        {\n            maxBombsDetonated = Math.Max(BFS(i),maxBombsDetonated);\n            if(maxBombsDetonated == n)\n            {\n                return n;\n            }\n        }\n        return maxBombsDetonated;          \n    }\n    public int BFS(int i)\n    {\n       // Travsering the adjacencyList in BFS manner \n       Queue<int> queue = new Queue<int>();\n       HashSet<int> visited = new HashSet<int>();\n\n       queue.Enqueue(i);\n       visited.Add(i);\n\n       while(queue.Count != 0)\n       {\n           int temp = queue.Dequeue();\n           foreach(int curr in adjacencyList[temp])\n           {\n               if(!visited.Contains(curr))\n               {\n                   queue.Enqueue(curr);\n                   visited.Add(curr);\n               }\n           }\n       }\n       return visited.Count;\n    }\n}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n```
['Breadth-First Search', 'Graph', 'C#']