2092. Find All People With Secret

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.

• union find solution
• Time : O(e + n)
• Space : O(e)

class Solution {
    map<int, vector<pair<int,int>>> buildMeetingMap(vector<vector<int>>& meetings) { //O(e)
        map<int, vector<pair<int,int>>> res;
        for(auto& meeting : meetings) {
            res[meeting[2]].push_back({meeting[0], meeting[1]});
        }
        return res;
    };

    int findParent(vector<int>& group, int n) {
        return group[n] == n ? n : group[n] = findParent(group, group[n]);
    }

    void merge(vector<int>& group, int a, int b) {
        int pa = findParent(group, a), pb = findParent(group, b);
        group[pa] = group[pb] = min(pa,pb);
    }

    int appendSecretPersonsPerMeeting(vector<pair<int, int>>& meetings, vector<int>& secretPersons, int n) { //O(v + e) = O(n + e) total
        unordered_set<int> participatedMembers;
        for(auto& [personA, personB] : meetings) {
            merge(secretPersons,personA,personB);
            participatedMembers.insert(personA);
            participatedMembers.insert(personB);
        }
        int secretPersonCount = 0;
        for(auto& member : participatedMembers) {
            secretPersonCount += (secretPersons[member] = findParent(secretPersons, member)) == 0;
            if(secretPersons[member]) secretPersons[member] = member;
        }
        return secretPersonCount;
    }
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        vector<int> secretPersons(n, -1);
        for(int i = 0; i < n; i++) {
            secretPersons[i] = i;
        }
        secretPersons[0] = secretPersons[firstPerson] = 0;

        map<int, vector<pair<int, int>>> meetingMap = buildMeetingMap(meetings);
        for(auto& [time, meetingList] : meetingMap) {
            int secretPersonCount = appendSecretPersonsPerMeeting(meetingList, secretPersons, n);
            if(secretPersonCount == n) break;
        }
        vector<int> res;
        for(int i = 0; i < n; i++) {
            if(!findParent(secretPersons, i))
                res.push_back(i);
        }
        return res;
    }
};

• bfs solution
• Time : O(e*logk)
• Space : O(v + e)

class Solution {
    vector<pair<bool,int>> history;
    map<int, vector<pair<int,int>>> buildMeetingMap(vector<vector<int>>& meetings) { //O(e)
        map<int, vector<pair<int,int>>> res;
        for(auto& meeting : meetings) {
            res[meeting[0]].push_back({meeting[2], meeting[1]});
            res[meeting[1]].push_back({meeting[2], meeting[0]});
        }
        return res;
    };

    void bfs(int person, int time, map<int,vector<pair<int,int>>>& meetings) {
        if(history[person].first and history[person].second <= time) return;
        int knownTime = time, beforeKnownTime = history[person].second;
        history[person].first = true;


        auto start = lower_bound(meetings[person].begin(), meetings[person].end(), make_pair(knownTime, INT_MIN));
        auto end = lower_bound(meetings[person].begin(), meetings[person].end(), make_pair(beforeKnownTime, INT_MIN));
        for(; start != end; start++) {
            bfs(start->second, start->first, meetings);
        }
    }
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        history = vector<pair<bool,int>> (n, {false, INT_MAX}); //know secret , time pair
        //history[0] = history[firstPerson] = {true, 0};
        map<int, vector<pair<int, int>>> meetingMap = buildMeetingMap(meetings);
        for(auto& [person, meetingList] : meetingMap) {
            sort(meetingList.begin(), meetingList.end());
        }

        bfs(0, 0, meetingMap);
        bfs(firstPerson, 0, meetingMap);

        vector<int> res;
        for(int i = 0; i < n; i++) {
            if(history[i].first)
                res.push_back(i);
        }
        return res;
    }
};