Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: medium В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi. Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b. Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1. Пример: Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4 Output: 3 Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends. 👨‍💻 Алгоритм: 1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они. 2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск": Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b). Каждое объединение добавляет новые связи между участниками. 3⃣Следите за количеством групп: Изначально каждый участник рассматривается как отдельная группа. Количество групп уменьшается с каждым полезным объединением. Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени. Если такого момента не существует, верните -1. 😎 Решение: class UnionFind { private var parent: [Int] private var rank: [Int] init(_ n: Int) { parent = Array(0..<n) rank = Array(repeating: 1, count: n) } func find(_ x: Int) -> Int { if parent[x] != x { parent[x] = find(parent[x]) } return parent[x] } func union(_ x: Int, _ y: Int) -> Bool { let rootX = find(x) let rootY = find(y) if rootX != rootY { if rank[rootX] > rank[rootY] { parent[rootY] = rootX } else if rank[rootX] < rank[rootY] { parent[rootX] = rootY } else { parent[rootY] = rootX rank[rootX] += 1 } return true } return false } } class Solution { func earliestAcq(_ logs: [[Int]], _ n: Int) -> Int { let sortedLogs = logs.sorted { &#036;0[0] < &#036;1[0] } var groupCount = n let uf = UnionFind(n) for log in sortedLogs { let timestamp = log[0] let friendA = log[1] let friendB = log[2] if uf.union(friendA, friendB) { groupCount -= 1 } if groupCount == 1 { return timestamp } } return -1 } } Ставь 👍 и забирай 📚 Базу знаний