# 1101 The Earliest Moment When Everyone Become Friends

There are n people in a social group labeled from `0` to `n - 1`. You are given an array `logs` where `logs[i] = [timestampi, xi, yi]` indicates that `xi` and `yi` will be friends at the time `timestampi`.

Friendship is symmetric. That means if `a` is friends with `b`, then `b` is friends with `a`. Also, person `a` is acquainted with a person `b` if `a` is friends with `b`, or `a` is a friend of someone acquainted with `b`.

Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return `-1`.

Example 1:

``````Input: logs = [
[20190101,0,1],
[20190104,3,4],
[20190107,2,3],
[20190211,1,5],
[20190224,2,4],
[20190301,0,3],
[20190312,1,2],
[20190322,4,5]
], n = 6
Output: 20190301

Explanation:
The first event occurs at timestamp = 20190101, and after 0 and 1 become friends,
we have the following friendship groups [0,1], [2], [3], [4], [5].

The second event occurs at timestamp = 20190104, and after 3 and 4 become friends,
we have the following friendship groups [0,1], [2], [3,4], [5].

The third event occurs at timestamp = 20190107, and after 2 and 3 become friends,
we have the following friendship groups [0,1], [2,3,4], [5].

The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends,
we have the following friendship groups [0,1,5], [2,3,4].

The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends,
nothing happens.

The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends,
we all become friends.
``````

Example 2:

``````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.
``````

Constraints:

• `2 <= n <= 100`
• `1 <= logs.length <= 104`
• `logs[i].length == 3`
• `0 <= timestampi <= 109`
• `0 <= xi, yi <= n - 1`
• `xi != yi`
• All the values `timestampi` are unique.
• All the pairs `(xi, yi)` occur at most one time in the input.

For each `(tx, x, y)` in logs, assuming `x < y`, merge persons in `y`'s group to `x`'s group, and remove `y`'s original group.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````class Solution: def earliestAcq(self, logs: List[List[int]], n: int) -> int: group_to_persons = defaultdict(set) person_to_group = {} for i in range(n): group_to_persons[i].add(i) person_to_group[i] = i for ts, x, y in sorted(logs, key=lambda x: x[0]): if x > y: x, y = y, x x_group = person_to_group[x] y_group = person_to_group[y] if x_group != y_group: for yy in group_to_persons[y_group]: person_to_group[yy] = x_group group_to_persons[x_group].add(yy) del group_to_persons[y_group] if len(group_to_persons) == 1: return ts return -1``````