The Earliest Moment When Everyone Become Friends: Union-Find Tìm Thời Điểm Mọi Người Kết Bạn

Đề bài: Có N người (0..N-1). Logs: [timestamp, id_A, id_B] cho biết A,B trở thành bạn lúc timestamp. Friendship là quan hệ bắc cầu (transitive). Tìm timestamp sớm nhất mà mọi người cùng một nhóm bạn. Không có thì -1.

Ví dụ: logs đã sort theo thời gian, N=6 → output 20190301.

Ý tưởng: Union-Find (DSU) + Sort Logs

1. Sort logs theo timestamp tăng dần.
2. Khởi tạo DSU N component.
3. Duyệt logs: union(A, B). Sau mỗi union, kiểm tra nếu component count = 1 → trả về timestamp hiện tại.
4. Hết logs mà chưa gộp hết → -1.

Code Python

class Solution:
    def earliestAcq(self, logs: list[list[int]], n: int) -> int:
        parent = list(range(n))
        size = [1] * n
        components = n
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            nonlocal components
            rx, ry = find(x), find(y)
            if rx == ry:
                return
            # Union by size
            if size[rx] < size[ry]:
                rx, ry = ry, rx
            parent[ry] = rx
            size[rx] += size[ry]
            components -= 1
        
        # Sort logs by timestamp
        logs.sort(key=lambda x: x[0])
        
        for timestamp, a, b in logs:
            union(a, b)
            if components == 1:
                return timestamp
        
        return -1

# Test
ob = Solution()
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]
]
print(ob.earliestAcq(logs, 6))  # 20190301

Phân tích

• Time: O(E log E) do sort (E = số logs). Union-Find gần O(1).
• Space: O(N).
• Path compression + union by size → hiệu năng tối ưu.

Kết luận

Bài toán "dynamic connectivity" kinh điển. Union-Find là cấu trúc dữ liệu chuẩn. Sort logs đảm bảo xử lý theo thứ tự thời gian.