Find All People With Secret
Problem
There are n people labeled 0 to n−1. Person 0 knows a secret and shares it with firstPerson at time 0, before anything else happens. You are also given a list where meetings[i] = [x, y, t] means persons x and y meet at time t (one person may attend several meetings at the same time).
If either attendee of a meeting knows the secret at time t, the other learns it instantly — and within one time instant the secret can keep hopping along any chain of simultaneous meetings. Return every person who knows the secret after all meetings end, in any order (n up to 10⁵, up to 10⁵ meetings, 1 ≤ firstPerson ≤ n−1, times ≥ 1).
n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3[0,1,3]def find_all_people(n, meetings, first_person):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
parent[find(b)] = find(a)
union(0, first_person)
meetings.sort(key=lambda m: m[2])
i = 0
while i < len(meetings):
j = i
while j < len(meetings) and meetings[j][2] == meetings[i][2]:
j += 1
for x, y, _ in meetings[i:j]: # union everyone meeting now
union(x, y)
for x, y, _ in meetings[i:j]: # cut groups missing the secret
if find(x) != find(0):
parent[x] = x
parent[y] = y
i = j
return [p for p in range(n) if find(p) == find(0)]function findAllPeople(n, meetings, firstPerson) {
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
};
const union = (a, b) => { parent[find(b)] = find(a); };
union(0, firstPerson);
meetings.sort((a, b) => a[2] - b[2]);
for (let i = 0; i < meetings.length; ) {
let j = i;
while (j < meetings.length && meetings[j][2] === meetings[i][2]) j++;
for (let k = i; k < j; k++) union(meetings[k][0], meetings[k][1]);
for (let k = i; k < j; k++) {
const [x, y] = meetings[k];
if (find(x) !== find(0)) { parent[x] = x; parent[y] = y; }
}
i = j;
}
return [...Array(n).keys()].filter((p) => find(p) === find(0));
}List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
union(parent, 0, firstPerson);
Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
for (int i = 0; i < meetings.length; ) {
int j = i;
while (j < meetings.length && meetings[j][2] == meetings[i][2]) j++;
for (int k = i; k < j; k++) union(parent, meetings[k][0], meetings[k][1]);
for (int k = i; k < j; k++)
if (find(parent, meetings[k][0]) != find(parent, 0)) {
parent[meetings[k][0]] = meetings[k][0];
parent[meetings[k][1]] = meetings[k][1];
}
i = j;
}
List<Integer> res = new ArrayList<>();
for (int p = 0; p < n; p++) if (find(parent, p) == find(parent, 0)) res.add(p);
return res;
}
int find(int[] parent, int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
void union(int[] parent, int a, int b) { parent[find(parent, b)] = find(parent, a); }class Solution {
vector<int> parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
void unite(int a, int b) { parent[find(b)] = find(a); }
public:
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
unite(0, firstPerson);
sort(meetings.begin(), meetings.end(),
[](auto& a, auto& b) { return a[2] < b[2]; });
for (int i = 0, m = (int)meetings.size(); i < m; ) {
int j = i;
while (j < m && meetings[j][2] == meetings[i][2]) j++;
for (int k = i; k < j; k++) unite(meetings[k][0], meetings[k][1]);
for (int k = i; k < j; k++)
if (find(meetings[k][0]) != find(0)) {
parent[meetings[k][0]] = meetings[k][0];
parent[meetings[k][1]] = meetings[k][1];
}
i = j;
}
vector<int> res;
for (int p = 0; p < n; p++) if (find(p) == find(0)) res.push_back(p);
return res;
}
};Explanation
The tricky part is that the secret spreads instantly within a single time instant: all meetings at the same time t form a temporary graph, and everyone in a connected component that touches a secret-holder learns it — even through a chain of simultaneous meetings. So we cannot process meetings one by one; we must process them grouped by time.
Sort the meetings by time and sweep over the groups. We keep a union-find (disjoint set) over the n people, seeded with union(0, firstPerson) for the time-0 share. Inside one time group we simply union(x, y) for every meeting — that builds exactly the temporary connectivity of this instant, so anyone whose root equals find(0) now knows the secret.
The key trick is the reset pass. When a time group ends, its temporary links must not leak into the future: two people who chatted without the secret are not still connected an hour later. So for each meeting of the group, if find(x) != find(0) the component never touched the secret, and we detach both attendees by pointing them back at themselves (parent[x] = x). Only this group's attendees were newly linked, so resetting them fully dissolves the loose component, while secret-holding unions are kept forever.
Default example: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3. After union(0, 3), the time-2 group unions 1 and 2, but their root differs from find(0), so both are reset. At time 3 the meetings (3,1) and (0,3) connect person 1 to the secret component. The final sweep collects everyone with find(p) == find(0): [0, 1, 3].
An equivalent view is a BFS per time group: build the instant's adjacency lists and flood outward from the attendees who already know the secret. Union-find does the same simulation with much lighter bookkeeping.
Sorting costs O(m log m) and dominates; each meeting then triggers a constant number of find/union calls, which are near-O(1) amortized thanks to path compression, and the final sweep over people is O(n).