Question

2092. Find All People With Secret

中文文档

Description

You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [xi, yi, timei] indicates that person xi and person yi have a meeting at timei. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person xi has the secret at timei, then they will share the secret with person yi, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return _a list of all the people that have the secret after all the meetings have taken place. _You may return the answer in any order.

 

Example 1:

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.​​​​
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2:

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3:

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

 

Constraints:

• 2 <= n <= 105
• 1 <= meetings.length <= 105
• meetings[i].length == 3
• 0 <= xi, yi <= n - 1
• xi != yi
• 1 <= timei <= 105
• 1 <= firstPerson <= n - 1

Solutions

Solution 1

class Solution:
  def findAllPeople(
    self, n: int, meetings: List[List[int]], firstPerson: int
  ) -> List[int]:
    vis = [False] * n
    vis[0] = vis[firstPerson] = True
    meetings.sort(key=lambda x: x[2])
    i, m = 0, len(meetings)
    while i < m:
      j = i
      while j + 1 < m and meetings[j + 1][2] == meetings[i][2]:
        j += 1
      s = set()
      g = defaultdict(list)
      for x, y, _ in meetings[i : j + 1]:
        g[x].append(y)
        g[y].append(x)
        s.update([x, y])
      q = deque([u for u in s if vis[u]])
      while q:
        u = q.popleft()
        for v in g[u]:
          if not vis[v]:
            vis[v] = True
            q.append(v)
      i = j + 1
    return [i for i, v in enumerate(vis) if v]

class Solution {
  public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
    boolean[] vis = new boolean[n];
    vis[0] = true;
    vis[firstPerson] = true;
    int m = meetings.length;
    Arrays.sort(meetings, Comparator.comparingInt(a -> a[2]));
    for (int i = 0; i < m;) {
      int j = i;
      for (; j + 1 < m && meetings[j + 1][2] == meetings[i][2]; ++j)
        ;
      Map<Integer, List<Integer>> g = new HashMap<>();
      Set<Integer> s = new HashSet<>();
      for (int k = i; k <= j; ++k) {
        int x = meetings[k][0], y = meetings[k][1];
        g.computeIfAbsent(x, key -> new ArrayList<>()).add(y);
        g.computeIfAbsent(y, key -> new ArrayList<>()).add(x);
        s.add(x);
        s.add(y);
      }
      Deque<Integer> q = new ArrayDeque<>();
      for (int u : s) {
        if (vis[u]) {
          q.offer(u);
        }
      }
      while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : g.getOrDefault(u, Collections.emptyList())) {
          if (!vis[v]) {
            vis[v] = true;
            q.offer(v);
          }
        }
      }
      i = j + 1;
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      if (vis[i]) {
        ans.add(i);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
    vector<bool> vis(n);
    vis[0] = vis[firstPerson] = true;
    sort(meetings.begin(), meetings.end(), [&](const auto& x, const auto& y) {
      return x[2] < y[2];
    });
    for (int i = 0, m = meetings.size(); i < m;) {
      int j = i;
      for (; j + 1 < m && meetings[j + 1][2] == meetings[i][2]; ++j)
        ;
      unordered_map<int, vector<int>> g;
      unordered_set<int> s;
      for (int k = i; k <= j; ++k) {
        int x = meetings[k][0], y = meetings[k][1];
        g[x].push_back(y);
        g[y].push_back(x);
        s.insert(x);
        s.insert(y);
      }
      queue<int> q;
      for (int u : s)
        if (vis[u])
          q.push(u);
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
          if (!vis[v]) {
            vis[v] = true;
            q.push(v);
          }
        }
      }
      i = j + 1;
    }
    vector<int> ans;
    for (int i = 0; i < n; ++i)
      if (vis[i])
        ans.push_back(i);
    return ans;
  }
};

func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
  vis := make([]bool, n)
  vis[0], vis[firstPerson] = true, true
  sort.Slice(meetings, func(i, j int) bool {
    return meetings[i][2] < meetings[j][2]
  })
  for i, j, m := 0, 0, len(meetings); i < m; i = j + 1 {
    j = i
    for j+1 < m && meetings[j+1][2] == meetings[i][2] {
      j++
    }
    g := map[int][]int{}
    s := map[int]bool{}
    for _, e := range meetings[i : j+1] {
      x, y := e[0], e[1]
      g[x] = append(g[x], y)
      g[y] = append(g[y], x)
      s[x], s[y] = true, true
    }
    q := []int{}
    for u := range s {
      if vis[u] {
        q = append(q, u)
      }
    }
    for len(q) > 0 {
      u := q[0]
      q = q[1:]
      for _, v := range g[u] {
        if !vis[v] {
          vis[v] = true
          q = append(q, v)
        }
      }
    }
  }
  var ans []int
  for i, v := range vis {
    if v {
      ans = append(ans, i)
    }
  }
  return ans
}

function findAllPeople(n: number, meetings: number[][], firstPerson: number): number[] {
  let parent: Array<number> = Array.from({ length: n + 1 }, (v, i) => i);
  parent[firstPerson] = 0;

  function findParent(index: number): number {
    if (parent[index] != index) parent[index] = findParent(parent[index]);
    return parent[index];
  }

  let map = new Map<number, Array<Array<number>>>();
  for (let meeting of meetings) {
    const time = meeting[2];
    let members: Array<Array<number>> = map.get(time) || new Array();
    members.push(meeting);
    map.set(time, members);
  }
  const times = [...map.keys()].sort((a, b) => a - b);
  for (let time of times) {
    // round 1
    for (let meeting of map.get(time)) {
      let [a, b] = meeting;
      if (!parent[findParent(a)] || !parent[findParent(b)]) {
        parent[findParent(a)] = 0;
        parent[findParent(b)] = 0;
      }
      parent[findParent(a)] = parent[findParent(b)];
    }
    // round 2
    for (let meeting of map.get(time)) {
      let [a, b] = meeting;
      if (!parent[findParent(a)] || !parent[findParent(b)]) {
        parent[findParent(a)] = 0;
        parent[findParent(b)] = 0;
      } else {
        parent[a] = a;
        parent[b] = b;
      }
    }
  }

  let ans = new Array<number>();
  for (let i = 0; i <= n; i++) {
    if (!parent[findParent(i)]) {
      ans.push(i);
    }
  }
  return ans;
}