Formatted question description: https://leetcode.ca/all/2092.html

2092. Find All People With Secret (Hard)

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] = [x_i, y_i, time_i] indicates that person x_i and person y_i have a meeting at time_i. 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 x_i has the secret at time_i, then they will share the secret with person y_i, 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.

Example 4:

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

Constraints:

2 <= n <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= x_i, y_i<= n - 1
x_i != y_i
1 <= time_i <= 10⁵
1 <= firstPerson <= n - 1

Similar Questions:

Reachable Nodes In Subdivided Graph (Hard)

Solution 1. Union Find

Sort meetings in ascending order of meeting time.

Visit the meetings happening at the same time together.

We can connect the two persons in the same meeting using a UnionFind.

Tricky point here: After traversing this batch of meetings, we reset the persons who don’t know the secret by checking if he/she is connected to person 0. With UnionFind, reseting means setting id[x] = x.

In the end, we add all the persons who are connected to person 0 into the answer array.

// OJ: https://leetcode.com/problems/find-all-people-with-secret/
// Time: O(MlogM + N) where `M` is the length of `meetings`
// Space: O(N)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int n) : id(n) {
        iota(begin(id), end(id), 0);
    }
    void connect(int a, int b) {
        id[find(b)] = find(a);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    bool connected(int a, int b) {
        return find(a) == find(b);
    }
    void reset(int a) { id[a] = a; }
};
class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& A, int firstPerson) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[2] < b[2]; }); // Sort the meetings in ascending order of meeting time
        int i = 0, M = A.size();
        UnionFind uf(n);
        uf.connect(0, firstPerson); // Connect person 0 with the first person
        vector<int> ppl;
        while (i < M) {
            ppl.clear();
            int time = A[i][2];
            while (i < M && A[i][2] == time) { // For all the meetings happending at the same time
                uf.connect(A[i][0], A[i][1]); // Connect the two persons
                ppl.push_back(A[i][0]); // Add both persons into the pool
                ppl.push_back(A[i][1]);
                ++i;
            }
            for (int n : ppl) { // For each person in the pool, check if he/she's connected with person 0.
                if (!uf.connected(0, n)) uf.reset(n); // If not, this person doesn't have secret, reset it.
            }
        }
        vector<int> ans;
        for (int j = 0; j < n; ++j) {
            if (uf.connected(0, j)) ans.push_back(j); // Push all the persons who are connected with person 0 into answer array
        }
        return ans;
    }
};

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]

############

# 2092. Find All People With Secret
# https://leetcode.com/problems/find-all-people-with-secret/

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        m = len(meetings)
        known = set([0])
        times = collections.defaultdict(list)
        
        for x, y, t in meetings:
            times[t].append((x, y))
        times[0].append((0, firstPerson))
        
        keys = sorted(times.keys())
        
        for t in keys:
            propagate = set()
            met = collections.defaultdict(set)
            
            for x, y in times[t]:
                if x in known:
                    propagate.add(x)
                if y in known:
                    propagate.add(y)
                    
                met[x].add(y)
                met[y].add(x)
            
            stack = list(propagate)
            while stack:
                x = stack.pop()
                
                for people in met[x]:
                    if people in propagate: continue
                    propagate.add(people)
                    known.add(people)
                    stack.append(people)
            
        return list(known)
        

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;
    }
}

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;
}

Discuss

https://leetcode.com/problems/find-all-people-with-secret/discuss/1599815/C%2B%2B-Union-Find

2092 - Find All People With Secret

2092. Find All People With Secret (Hard)

Solution 1. Union Find

Discuss

All Problems

All Solutions

Welcome to Subscribe On Youtube

2092. Find All People With Secret (Hard)

Solution 1. Union Find

Discuss

All Problems

All Solutions