Minimize Malware Spread LeetCode solution in C++

1
class Solution {
2
 public:
3
  void dfs(int i, int n, vector<bool> &visited, vector<int> &cur, map<int, int> &ind, int &cnt,
4
           map<int, vector<int>> &mp) {
5
    if (!visited[i]) {
6
      visited[i] = true;
7
      cur.push_back(i);
8
      ind[i] = cnt;
9
      for (int j = 0; j < mp[i].size(); j++) {
10
        dfs(mp[i][j], n, visited, cur, ind, cnt, mp);
11
      }
12
    }
13
  }
14
  int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial) {
15
    int n = graph.size();
16
    map<int, vector<int>> mp; // Adjacency list creation for the graph
17
    for (int i = 0; i < n; i++) {
18
      for (int j = 0; j < n; j++) {
19
        if (i != j && graph[i][j] == 1) mp[i].push_back(j);
20
      }
21
    }
22
    map<int, int> ind;              // This map is for storing the component number to which
23
                                    // a particular node belongs to
24
    vector<vector<int>> v;          // Store all the connected components
25
    vector<bool> visited(n, false); // Visited array to keep track of the visited nodes
26
    int cnt = 0;                    // Current component number
27
    for (int i = 0; i < n; i++) {
28
      if (!visited[i]) {
29
        vector<int> cur;
30
        dfs(i, n, visited, cur, ind, cnt,
31
            mp); // Dfs call for getting single components
32
        cnt++;
33
        v.push_back(cur);
34
      }
35
    }
36
    map<int, vector<int>> help; // This map tells that how many node that is present in inital
37
                                // vector are of same component
38
    for (int i = 0; i < initial.size(); i++) {
39
      int index = ind[initial[i]];
40
      help[index].push_back(initial[i]);
41
    }
42
    int sz = INT_MIN;
43
    int ans = n; // This loop is based on the logic described above
44
    for (auto it = help.begin(); it != help.end(); it++) {
45
      if (help[it->first].size() == 1) {
46
        int cover = v[it->first].size();
47
        if (cover > sz) {
48
          sz = cover;
49
          ans = help[it->first][0];
50
        } else if (cover == sz) {
51
          if (help[it->first][0] < ans) ans = help[it->first][0];
52
        }
53
      }
54
    }
55
    if (ans != n) return ans;
56
    for (int i = 0; i < initial.size(); i++) ans = min(ans, initial[i]);
57
    return ans;
58
  }
59
};