彼此熟识的最早时间

Problem

In a social circle, there are \(n\) people, numbered from 0 to \(n - 1\). Now there is a list of logs logs, where logs[i] = [time, \(x\), \(y\)] indicates that \(x\) and \(y\) became friends with each other at time.

Friendship is mutual and transferable. That is:

• Mutual: when \(a\) and \(b\) are friends, then \(b\) has \(a\) among their friends.
• Transferable: when \(a\) and \(b\) are friends, and \(b\) has \(c\) as a friend, then \(a\) and \(c\) will also be friends and know each other.

Return the earliest time when everyone in this circle knew each other. If the earliest time is not found, -1 is returned.

Example 1:

Input: logs =
[[20220101,0,1],
[20220109,3,4],
[20220304,0,4],
[20220305,0,3],
[20220404,2,4]],
n = 5

Output: 20220404

Explanation:

time = 20220101, 0 and 1 have become friends with [0,1], [2], [3], [4]

time = 20220109, 3 and 4 have become friends with [0,1], [2], [3,4]

time = 20220304, 0 and 4 have become friends with [0,1,3,4], [2]

time = 20220305, 0 and 3 already friends

time = 20220404, 2 and 4 have become friends with [0,1,2,3,4]

Example 2:

Input: logs =
[[7,3,1],
[3,0,3],
[2,0,1],
[1,1,2],
[5,3,2]],
n = 4

Output: 3

Constraints:

• 2 <= \(n\) <= 100
• 1 <= logs.length <= \(10^4\)
• logs[i][1] != logs[i][2]
• In the logs, there will be no duplicate elements for a given time.

Idea

Treat each person as a node and each log as an edge that merges two friend groups. Sort the logs by time and process them in order with Union-Find (disjoint set), keeping a counter of the remaining groups, which starts at \(n\).

For each log, if \(x\) and \(y\) have different roots, union their groups and decrease the counter by 1. The first time the counter reaches 1, everyone knows each other, so return that time. If all logs are used and more than one group is left, return -1.

Time complexity: \(O(m \log m + m \cdot \alpha(n))\), Space complexity: \(O(n)\), where \(m\) is the number of logs and \(\alpha\) is the inverse Ackermann function (almost constant)

Pseudo Code

def earliest_acq(logs, n):
    logs.sort()                          # sort by time
    parent = list(range(n))
    size = [1] * n
    groups = n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # path compression
            x = parent[x]
        return x

    for time, x, y in logs:
        root_x, root_y = find(x), find(y)
        if root_x == root_y:
            continue                     # already friends
        if size[root_x] < size[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_y] = root_x          # union by size
        size[root_x] += size[root_y]
        groups -= 1
        if groups == 1:
            return time

    return -1