[C#] BFS Graph Traversal
Intuition\nPorted from Java from: https://leetcode.com/problems/detonate-the-maximum-bombs/solutions/1623563/simple-java-bfs/?page=3\n# Approach\nDue to its rad
# Intuition\nPorted from Java from: https://leetcode.com/problems/detonate-the-maximum-bombs/solutions/1623563/simple-java-bfs/?page=3\n# Approach\nDue to its radial exploration nature, BFS almost litteraly fits this problem. I confess I did try first Union-Find, but could only get 125 of LeetCode\'s test cases to pass...\n\nThe first part of the BFS solution consists in computing the indiviual reach of each bomb (using Euclidean distance) and storing it in a dictionary. Note that bombs that don\'t reach any other bombs are not added to the dictonary:\n\n```\nDictionary<int,List<int>> map = new ();\n\nfor(int i=0; i < bombs.Length;i++){\n    for(int j=0; j< bombs.Length;j++){\n        if(j==i) \n            continue;\n        long sum = (long)(bombs[i][0]-bombs[j][0])*(long)(bombs[i][0]-bombs[j][0])+(long)(bombs[i][1]-bombs[j][1])*(long)(bombs[i][1]-bombs[j][1]);\n        long self = (long)bombs[i][2]*(long)bombs[i][2];\n        if(self >= sum){\n            if(!map.ContainsKey(i)){\n                map.Add(i,new List<int>());\n            }\n            map[i].Add(j);\n        }\n    }\n}\n```\nThe second par is BFS itself. Note that the visited array is reset for every new starting node/traversal.\n```\nfor(int i=0;i< bombs.Length;i++){\n...\n    int[] visit = new int[bombs.Length];\n```\nAt the end of each traversal, the maximum bomb reach is updated:\n```\nmax = Math.Max(max,count);\n\n```\nBFS will allow us to accumulate and explore the reach of each bomb. Each traversal will be optmized since we\'ll avoid repeated operations by marking the visited nodes. \nThe fact that we already have a precomputed dictionary with the individual reach of each bomb also makes a huge performance difference when running the BFS traversal for each bomb.\n\n# Code\n```\npublic class Solution {\n\n    public int MaximumDetonation(int[][] bombs) {\n        Dictionary<int,List<int>> map = new ();\n        \n        for(int i=0; i < bombs.Length;i++){\n            for(int j=0; j< bombs.Length;j++){\n                if(j==i) \n                    continue;\n                long sum = (long)(bombs[i][0]-bombs[j][0])*(long)(bombs[i][0]-bombs[j][0])+(long)(bombs[i][1]-bombs[j][1])*(long)(bombs[i][1]-bombs[j][1]);\n                long self = (long)bombs[i][2]*(long)bombs[i][2];\n                if(self >= sum){\n                    if(!map.ContainsKey(i)){\n                        map.Add(i,new List<int>());\n                    }\n                    map[i].Add(j);\n                }\n            }\n        }\n        int max = 1;\n        \n        for(int i=0;i< bombs.Length;i++){\n            if(!map.ContainsKey(i)){\n                continue;\n            }\n            int[] visit = new int[bombs.Length];\n            int count = 1;\n            Queue<int> q = new ();\n            q.Enqueue(i);\n            visit[i] = 1;\n            while(q.Count > 0){\n                int size = q.Count;\n                while(size > 0){\n                    int cur = q.Dequeue();\n                    if(!map.ContainsKey(cur)){\n                        size--;\n                        continue;\n                    }\n                    foreach(int x in map[cur]){\n                        if(visit[x]==1) \n                            continue;\n                        q.Enqueue(x);\n                        visit[x] = 1;\n                        count++;\n                    }\n                    size--;\n                }\n            }\n            max = Math.Max(max,count);\n        }\n        return max;\n    }\n}\n```
['Breadth-First Search', 'C#']