Description

Submission

class Solution {
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();
        vector<vector<int>> graph(n);

        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                long long dx = bombs[i][0] - bombs[j][0];
                long long dy = bombs[i][1] - bombs[j][1];
                long long dSquared = dx * dx + dy * dy;
                if((long long)bombs[i][2] * bombs[i][2] >= dSquared) graph[i].push_back(j);
                if((long long)bombs[j][2] * bombs[j][2] >= dSquared) graph[j].push_back(i);
            }
        }

        int ret = 0;
        for(int i = 0; i < n; ++i) {
            vector<int> visited(n, 0);
            queue<int> q;
            q.push(i);
            int count = 0;
            while(!q.empty()) {
                int cur = q.front();
                q.pop();

                if(visited[cur]) continue;
                visited[cur] = 1;
                ++count;

                for(int nextNode: graph[cur]) {
                    if(!visited[nextNode]) q.push(nextNode);
                }
            }
            ret = max(ret, count);
        }

        return ret;
    }
};

// preprocess:
// 2 layer loop, n^2

// for each bomb:
//     dfs/bfs

// n^2

// O(n^2)