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.

&nbsp;
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.


&nbsp;
Constraints:


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


class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:

        class UnionFind:
            def __init__(self):
                self.parents = {}
                self.ranks = {}

            def insert(self, x):
                if x not in self.parents:
                    self.parents[x] = x
                    self.ranks[x] = 0

            def find_parent(self, x):
                if self.parents[x] != x:
                    self.parents[x] = self.find_parent(self.parents[x])
                return self.parents[x]

            def union(self, x, y):
                self.insert(x)
                self.insert(y)
                x, y = self.find_parent(x), self.find_parent(y)
                if x == y:
                    return
                if self.ranks[x] > self.ranks[y]:
                    self.parents[y] = x
                else:
                    self.parents[x] = y
                    if self.ranks[x] == self.ranks[y]:
                        self.ranks[y] += 1

        time2meets = defaultdict(list)
        for x, y, t in meetings:
            time2meets[t].append((x, y))
        time2meets = sorted(time2meets.items())

        curr_know = set([0, firstPerson])

        for time, meets in time2meets:
            uf = UnionFind()
            for x, y in meets:
                uf.union(x, y)

            groups = defaultdict(set)
            for idx in uf.parents:
                groups[uf.find_parent(idx)].add(idx)

            for group in groups.values():
                if group & curr_know:
                    curr_know.update(group)

        return list(curr_know)
class Solution {
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
	
		// create <time, index> map
        Map<Integer, List<Integer>> timeToIndexes = new TreeMap<>();
        int m = meetings.length;
        for (int i = 0; i < m; i++) {
            timeToIndexes.putIfAbsent(meetings[i][2], new ArrayList<>());
            timeToIndexes.get(meetings[i][2]).add(i);
        }
		
        UF uf = new UF(n);
		// base
        uf.union(0, firstPerson);
		
		// for every time we have a pool of people that talk to each other
		// if someone knows a secret proir to this meeting - all pool will too
		// if not - reset unions from this pool
        for (int time : timeToIndexes.keySet()) {
            Set<Integer> pool = new HashSet<>();
			
            for (int ind : timeToIndexes.get(time)) {
                int[] currentMeeting = meetings[ind];
                uf.union(currentMeeting[0], currentMeeting[1]);
                pool.add(currentMeeting[0]);
                pool.add(currentMeeting[1]);
            }
			
			// meeting that took place now should't affect future
			// meetings if people don't know the secret
            for (int i : pool) if (!uf.connected(0, i)) uf.reset(i);
        }
		
		// if the person is conneted to 0 - they know a secret
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) if (uf.connected(i,0)) ans.add(i);
        return ans;
    }
    
	// regular union find
    private static class UF {
        int[] parent, rank;
		
        public UF(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);

            if (rootP == rootQ)
                return;

            if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
            } else {
                parent[rootQ] = rootP;
                rank[rootP]++;
            }
        }
        
        public int find(int p) {
            while (parent[p] != p) {
                p = parent[parent[p]];
            }
            return p;
        }
        
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
        
        public void reset(int p) {
            parent[p] = p;
            rank[p] = 0;
        }
    }
}
class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        vector<int> res;
        set<int> ust;
        ust.insert(0);
        ust.insert(firstPerson);
        map<int,vector<pair<int,int>>> mp;
        for (auto &m : meetings) {
            mp[m[2]].push_back({m[0],m[1]});
        }
        for (auto &m : mp) {
            for (auto &v : m.second) { //front to back
                if (ust.count(v.first)) {
                    ust.insert(v.second);
                }
                if (ust.count(v.second)) {
                    ust.insert(v.first);
                }
            }
            for (auto it = m.second.rbegin(); it != m.second.rend(); ++it) { //back to front
                if (ust.count((*it).first)) {
                    ust.insert((*it).second);
                }
                if (ust.count((*it).second)) {
                    ust.insert((*it).first);
                }
            }
        }
        for (auto it = ust.begin(); it != ust.end(); ++it)
            res.push_back(*it);
        return res;
    }
};
var findAllPeople = function(n, meetings, firstPerson) {
    const timeToMeeting = mapSortedTimeToMeetings(meetings);

    const peopleThatCurrentlyHaveSecret = new Set([0, firstPerson]);
    for (const peopleInMeetings of timeToMeeting.values()) {
        const personToMeetingsWithPeople =
            mapPeopleToPeopleTheyAreHavingMeetingsWith(peopleInMeetings);
        let peopleInMeetingsWithSecret =
            findPeopleThatHaveTheSecret(peopleInMeetings, peopleThatCurrentlyHaveSecret);

        // BFS algorithm
        while (peopleInMeetingsWithSecret.size > 0) {
            const nextPeopleInMeetingsWithSecret = new Set();
            for (const attendee of peopleInMeetingsWithSecret) {
                for (const personInMeetingWithAttendee of personToMeetingsWithPeople[attendee]) {

                    // only add new people that have the secret otherwise there will be an
                    // infinite loop
                    if (!peopleThatCurrentlyHaveSecret.has(personInMeetingWithAttendee)) {
                        nextPeopleInMeetingsWithSecret.add(personInMeetingWithAttendee);
                        peopleThatCurrentlyHaveSecret.add(personInMeetingWithAttendee);
                    }
                }
            }
            peopleInMeetingsWithSecret = nextPeopleInMeetingsWithSecret;
        }
    }
    return [...peopleThatCurrentlyHaveSecret];
};

// groups all the meetings by time
// keys (time) is sorted in ascending order
function mapSortedTimeToMeetings(meetings) {
    meetings.sort((a, b) => a[2] - b[2]);

    const timeToMeeting = new Map();
    for (const [person1, person2, time] of meetings) {
        if (!timeToMeeting.has(time)) {
            timeToMeeting.set(time, []);
        }
        timeToMeeting.get(time).push([person1, person2]);
    }
    return timeToMeeting;
}

// creates an adjacency list of people and people they are having meetings with
function mapPeopleToPeopleTheyAreHavingMeetingsWith(peopleInMeetings) {
    const personToMeetingsWithPeople = {};
    for (const [person1, person2] of peopleInMeetings) {
        if (!personToMeetingsWithPeople[person1]) {
            personToMeetingsWithPeople[person1] = [];
        }
        if (!personToMeetingsWithPeople[person2]) {
            personToMeetingsWithPeople[person2] = [];
        }
        personToMeetingsWithPeople[person1].push(person2);
        personToMeetingsWithPeople[person2].push(person1);
    }
    return personToMeetingsWithPeople;
}

// finds all the people that are in meetings that have the secret
// set data structue is used so that people are not duplicated
function findPeopleThatHaveTheSecret(peopleInMeetings, peopleThatCurrentlyHaveSecret) {
    const peopleInMeetingsWithSecret = new Set();
    for (const peopleInMeeting of peopleInMeetings) {
        for (const person of peopleInMeeting) {
            if (peopleThatCurrentlyHaveSecret.has(person)) {
                peopleInMeetingsWithSecret.add(person);
            }
        }
    }
    return peopleInMeetingsWithSecret;
}
Find All People With Secret