<p>You are given an integer <code>n</code> indicating there are <code>n</code> people numbered from <code>0</code> to <code>n - 1</code>. You are also given a <strong>0-indexed</strong> 2D integer array <code>meetings</code> where <code>meetings[i] = [x<sub>i</sub>, y<sub>i</sub>, time<sub>i</sub>]</code> indicates that person <code>x<sub>i</sub></code> and person <code>y<sub>i</sub></code> have a meeting at <code>time<sub>i</sub></code>. A person may attend <strong>multiple meetings</strong> at the same time. Finally, you are given an integer <code>firstPerson</code>.</p>

<p>Person <code>0</code> has a <strong>secret</strong> and initially shares the secret with a person <code>firstPerson</code> at time <code>0</code>. 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 <code>x<sub>i</sub></code> has the secret at <code>time<sub>i</sub></code>, then they will share the secret with person <code>y<sub>i</sub></code>, and vice versa.</p>

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

<p>Return <em>a list of all the people that have the secret after all the meetings have taken place. </em>You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
<strong>Output:</strong> [0,1,2,3,5]
<strong>Explanation:
</strong>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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
<strong>Output:</strong> [0,1,3]
<strong>Explanation:</strong>
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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
<strong>Output:</strong> [0,1,2,3,4]
<strong>Explanation:</strong>
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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= meetings.length &lt;= 10<sup>5</sup></code></li>
	<li><code>meetings[i].length == 3</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i </sub>&lt;= n - 1</code></li>
	<li><code>x<sub>i</sub> != y<sub>i</sub></code></li>
	<li><code>1 &lt;= time<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= firstPerson &lt;= n - 1</code></li>
</ul>

from collections import deque, defaultdict
class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        secrets = set([0, firstPerson])
        time_map = {}
        
        for src, dst, t in meetings:
            if t not in time_map:
                time_map[t] = defaultdict(list)
            time_map[t][src].append(dst)
            time_map[t][dst].append(src)
        
        def dfs(src, adj):
            if src in visit:
                return 
        
            visit.add(src)
            secrets.add(src)
            for nei in adj[src]:
                dfs(nei, adj)
            
        for time in sorted(time_map.keys()):
            visit = set()
            for src in time_map[time]:
                if src in secrets:
                    dfs(src, time_map[time])
        return list(secrets)
        

        # Context 
            # n people, meetings array 
                # meetings array: at time x, multiple meetings at the same time.
                # bidirectional sharing? x --> y, y --> x, yes 
                # sorted by time? no
            # person 0 to first person at time 0. 
            # return list of all people with secret 
            # time involved
            # do until all meetings are done. 
        
        # input: n = 6 (0 - 5), meetings = [[1,2,5],[2,3,8],[1,5,10]], first person = 1
        # output: [0, 1, 2, 3, 5]
        
        # considerations
            # people can join multiple meetings at same time. 
            # connection nodes?
        
        
        
            # return list of people with secret
            
        
        # approach:
        # sort by the time meetings
#         withSecret = set() 
#         withSecret.add(0)
#         withSecret.add(firstPerson)
#         meetings.sort(key=lambda x: x[2])  # ascending
#         meetingsQueue = deque(meetings)
        
#         def relatedPeople(meetingsList):
#             # print("meetingsList: ", meetingsList)
#             connectionsGraph = defaultdict(list)  # key: p1 value: list of p2s in meetings
#             tellers = deque([])
#             newlyAdded = set()
#             # build the connections graph
#             for p1, p2, time in meetingsList:
#                 if p1 in withSecret:
#                     tellers.append(p1)
#                 if p2 in withSecret:
#                     tellers.append(p2)
                
#                 connectionsGraph[p1].append(p2)
#                 connectionsGraph[p2].append(p1)

#             # traverse: bfs: starting with people with secret: queue? 
#             while tellers:
#                 # breadth traversal
#                 for i in range(len(tellers)):
#                     teller = tellers.popleft()
#                     talkedPeople = connectionsGraph[teller] 
                    
#                     for toldPerson in talkedPeople:
#                         if toldPerson not in withSecret and toldPerson not in newlyAdded:
#                             tellers.append(toldPerson)
#                             newlyAdded.add(toldPerson)
                                  
#             return newlyAdded

#         # print("Meetings: ", meetingsQueue)
#         while meetingsQueue:
#             # within the same time frame 
#             currMeetings = [] 
#             currMeetings.append(meetingsQueue.popleft())
#             while meetingsQueue and currMeetings[0][2] == meetingsQueue[0][2]:
#                 currMeetings.append(meetingsQueue.popleft())
                
#             learnedSecret = relatedPeople(currMeetings)
#             withSecret.update(learnedSecret)
#         return list(withSecret)
            

                # [2,3,1], [1,2,1], [4, 5, 1]  --> build a bidirectional connections graph
                            # bfs on this graph, to find all affected nodes. 
        
            # implementaiton    
                # sort by meeting time 
                # group meetings by meeting time 
                    # helper function: create a bidirectional graph 
                #update all people with secret
        
71901