Найти всех людей с секретом

Вам дано целое число 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)]
Войдите в полноэкранный режим Выйти из полноэкранного режима

Оцените статью
Procodings.ru
Добавить комментарий