Find All People With Secret LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> findAllPeople(int n, vector<vector<int>> &meetings, int firstPerson) {
4
    // create the graph betwen the persons
5
    vector<vector<pair<int, int>>> graph(n);
6
    for (int i = 0; i < meetings.size(); ++i) {
7
      graph[meetings[i][0]].push_back({meetings[i][1], meetings[i][2]});
8
      graph[meetings[i][1]].push_back({meetings[i][0], meetings[i][2]});
9
    }
10

11
    // using min heap , using time as the sort order key.
12
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
13

14
    // Add both 0 and firstPerson in the queue as they know the secret initially
15
    // at time 0
16
    q.push({0, firstPerson});
17
    q.push({0, 0});
18
    //  vector to store res
19
    vector<int> res;
20

21
    // marking the persons as visited if they have met and shared the secret to
22
    // all possible persons they could
23
    vector<bool> visited(n, false);
24

25
    while (!q.empty()) {
26
      pair<int, int> curr = q.top();
27
      q.pop();
28

29
      int person = curr.second;
30
      int time = curr.first;
31

32
      // person had already shared the secret with others
33
      if (visited[person]) {
34
        continue;
35
      }
36
      visited[person] = true;
37

38
      // iterate all the meetings of this person and add the potential new
39
      // persons he can share secret with
40
      for (pair<int, int> neigh : graph[person]) {
41
        if (!visited[neigh.first] && time <= neigh.second) {
42
          q.push({neigh.second, neigh.first});
43
        }
44
      }
45
    }
46

47
    // all visited persons know the secret
48
    for (int i = 0; i < n; ++i) {
49
      if (visited[i]) {
50
        res.push_back(i);
51
      }
52
    }
53
    return res;
54
  }
55
};