LC 2092 [H] Find All People With Secret - ALawliet/algorithms GitHub Wiki
class Solution:
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
knows_secret = {0, firstPerson} # acts as visited set
time = lambda x: x[2] # x, y, [time]
meetings_sorted_by_time = sorted(meetings, key=time)
meetings_grouped_by_time_sorted_by_time = groupby(meetings_sorted_by_time, key=time)
for _time, group in meetings_grouped_by_time_sorted_by_time:
Q = set()
G = defaultdict(list)
for x, y, _time in group:
G[x].append(y) ; G[y].append(x)
# only want to queue people who know the secret
if x in knows_secret: Q.add(x)
if y in knows_secret: Q.add(y)
# in the loop: BFS each group
Q = deque(Q)
while Q:
x = Q.popleft()
for y in G[x]:
if y not in knows_secret:
knows_secret.add(y)
Q.append(y)
return knows_secret