Detonate the Maximum Bombs LeetCode solution in C++

1
class Solution {
2
 public:
3
  double eucDis(int x1, int y1, int x2, int y2) {
4
    double temp = pow(x1 - x2, 2) + pow(y1 - y2, 2);
5
    return sqrt(temp);
6
  }
7
  void dfs(int node, vector<int> &vis, vector<int> graph[], int &c) {
8
    c++;
9
    vis[node] = 1;
10
    for (auto i : graph[node]) {
11
      if (!vis[i]) {
12
        dfs(i, vis, graph, c);
13
      }
14
    }
15
  }
16
  int maximumDetonation(vector<vector<int>> &bombs) {
17
    int n = bombs.size();
18
    vector<int> graph[n + 1];
19
    int i, j;
20
    for (i = 0; i < n; i++) {
21
      bombs[i].push_back(i);
22
    }
23
    for (i = 0; i < n; i++) {
24
      for (j = 0; j < n; j++) {
25
        if (i == j) continue;
26
        double dis1 = eucDis(bombs[i][0], bombs[i][1], bombs[j][0], bombs[j][1]);
27

28
        if (dis1 <= bombs[i][2]) {
29
          int node1 = bombs[i][3];
30
          int node2 = bombs[j][3];
31
          graph[node1].push_back(node2);
32
        }
33
      }
34
    }
35

36
    int maxi = 1;
37
    for (i = 0; i < n; i++) {
38
      int c = 0;
39
      if (graph[i].empty()) continue;
40
      vector<int> vis(n + 1, 0);
41

42
      dfs(i, vis, graph, c);
43
      maxi = max(maxi, c);
44
    }
45
    return maxi;
46
  }
47
};