The Earliest Moment When Everyone Become Friends: Union-Find หาเวลาทุกคนเพื่อนกัน

โจทย์

มี N คน (id 0..N-1) และ logs [timestamp, id_A, id_B] แสดงเวลาที่ A และ B กลายเป็นเพื่อน มิติ "acquainted" แบบ transitive (เพื่อนของเพื่อน = เพื่อน) หา timestamp แรก ที่ทุกคน acquainted กันหมด (connected component = 1) ถ้าไม่มี → -1

ตัวอย่าง: N=6, 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]] → Output: 20190301

อัลกอริทึม: Union-Find (DSU) + Sort by Time

1. เรียง logs ตาม timestamp น้อย→มาก
2. Init DSU: แต่ละคนเป็น component แยกกัน (N components)
3. Iterate logs: union(A, B) ถ้า union สำเร็จ (merge 2 components) → components--
4. เมื่อ components == 1 → คืน timestamp นั้น

การติดตั้ง (Python Implementation)

class Solution:
    def earliestAcq(self, logs: list[list[int]], n: int) -> int:
        # Union-Find with path compression + union by size
        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
            px, py = find(x), find(y)
            if px == py:
                return False
            # Union by size
            if size[px] < size[py]:
                px, py = py, px
            parent[py] = px
            size[px] += size[py]
            components -= 1
            return True
        
        # Sort by timestamp
        logs.sort(key=lambda x: x[0])
        
        for timestamp, a, b in logs:
            if union(a, b):
                if components == 1:
                    return timestamp
        
        return -1

# ทดสอบ
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

Output

20190301

การทำงานทีละขั้น (Step by Step)

Complexity

• Time: O(E log E) สำหรับ sort + O(E α(N)) สำหรับ DSU
• Space: O(N) สำหรับ parent/size arrays

สรุป

โจทย์หาเวลาที่ graph กลายเป็น connected (single component) ใช้ Union-Find + Sort by time เป็นวิธีมาตรฐานและมีประสิทธิภาพ

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ