Minimize Malware Spread II LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial) {
4
    sort(initial.begin(), initial.end());
5
    int ans = -1, mn = INT_MAX, n = graph.size();
6

7
    vector<vector<int>> new_graph(n);
8
    for (int i = 0; i < n; i++)
9
      for (int j = 0; j < n; j++)
10
        if (graph[i][j]) new_graph[i].push_back(j);
11

12
    for (auto &k : initial) {
13
      vector<int> dsu(n, -1);
14
      for (int i = 0; i < n; i++)
15
        for (auto &j : new_graph[i])
16
          if (i != k && j != k) {
17
            int a = findParent(dsu, i), b = findParent(dsu, j);
18
            if (a != b) dsu[b] += dsu[a], dsu[a] = b;
19
          }
20

21
      vector<int> infected(n, 0);
22
      for (auto &i : initial)
23
        if (i != k) infected[findParent(dsu, i)]++;
24

25
      int total_infected = 0;
26
      for (int i = 0; i < n; i++)
27
        if (infected[i]) total_infected += abs(dsu[i]);
28

29
      if (total_infected < mn) mn = total_infected, ans = k;
30
    }
31

32
    return ans == -1 ? initial[0] : ans;
33
  }
34

35
  int findParent(vector<int> &dsu, int i) {
36
    int a = i;
37
    while (dsu[i] >= 0) i = dsu[i];
38

39
    if (i != a) dsu[a] = i;
40

41
    return i;
42
  }
43
};