Вам дано целое число n
, указывающее на существование n
людей, пронумерованных от 0
до n - 1
. Вам также дан двумерный целочисленный массив meetings
с индексом 0, где meetings[i] = [xi, yi, timei]
указывает, что человек xi
и человек yi
имеют встречу в timei
. Человек может присутствовать на нескольких встречах одновременно. Наконец, дается целое число firstPerson
.
Лицо 0
имеет секрет и первоначально делится секретом с лицом firstPerson
в момент времени 0
. Затем этот секрет передается каждый раз, когда происходит встреча с человеком, у которого есть этот секрет. Более формально, для каждой встречи, если человек xi
имеет секрет в timei
, то он поделится секретом с человеком yi
, и наоборот.
Секреты передаются мгновенно. То есть, человек может получить секрет и поделиться им с людьми на других встречах в течение того же временного интервала.
Верните список всех людей, владеющих секретом, после проведения всех встреч. Вы можете вернуть ответ в любом порядке.
Пример 1:
Вход: n = 6, встречи = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Выходные данные: [0,1,2,3,5]
Пояснение:
В момент времени 0 человек 0 делится секретом с человеком 1.
В момент времени 5 человек 1 делится секретом с человеком 2.
В момент времени 8 человек 2 делится секретом с человеком 3.
В момент времени 10 человек 1 делится секретом с человеком 5.
Таким образом, люди 0, 1, 2, 3 и 5 знают секрет после всех встреч.
Пример 2:
Вход: n = 4, встречи = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Выходные данные: [0,1,3]
Пояснение:
В момент времени 0 человек 0 делится секретом с человеком 3.
В момент времени 2 ни человек 1, ни человек 2 не знают секрета.
В момент времени 3 человек 3 делится секретом с человеком 0 и человеком 1.
Таким образом, люди 0, 1 и 3 знают секрет после всех встреч.
Пример 3:
Вход: n = 5, встречи = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Выходные данные: [0,1,2,3,4]
Пояснение:
В момент времени 0 человек 0 делится секретом с человеком 1.
В момент времени 1 человек 1 делится секретом с человеком 2, а человек 2 делится секретом с человеком 3.
Обратите внимание, что человек 2 может поделиться секретом одновременно с его получением.
В момент времени 2 человек 3 делится секретом с человеком 4.
Таким образом, люди 0, 1, 2, 3 и 4 знают секрет после всех встреч.
Ограничения:
-
2 <= n <= 105
. -
1 <= meetings.length <= 105
-
meetings[i].length == 3
-
0 <= xi, yi <= n - 1
-
xi != yi
-
1 <= timei <= 105
-
1 <= firstPerson <= n - 1
РЕШЕНИЕ:
from collections import defaultdict
class Solution:
def getParent(self, parent, x):
if parent[x] == x:
return x
parent[x] = self.getParent(parent, parent[x])
return parent[x]
def connect(self, parent, a, b):
parent[self.getParent(parent, a)] = self.getParent(parent, b)
def isConnected(self, parent, a, b):
return self.getParent(parent, a) == self.getParent(parent, b)
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
parent = list(range(n))
meets = defaultdict(list)
for a, b, t in meetings:
meets[t].append((a, b))
self.connect(parent, 0, firstPerson)
people = set()
for t in sorted(meets.keys()):
people.clear()
for a, b in meets[t]:
self.connect(parent, a, b)
people.update({a, b})
for p in people:
if not self.isConnected(parent, p, 0):
parent[p] = p
return [i for i in range(n) if self.isConnected(parent, i, 0)]