Union-find คืออะไร และใช้ที่ไหน?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) ติดตามการแบ่งสมาชิกออกเป็น **เซตที่แยกจากกัน** และรองรับการดำเนินการสองอย่างที่เกือบ O(1): **find** (x อยู่ในเซตไหน?) และ **union** (รวมเซตสองเซต) มันเยี่ยมสำหรับแบบสอบถาม **การเชื่อมต่อ**

## แนวคิด

แต่ละเซตเป็นต้นไม้ที่มีราก ด้วย **path compression** และ **union by rank/size** การดำเนินการทำงานในเวลา **amortized** เกือบคงที่ (inverse Ackermann, α(n))

## ตัวอย่าง

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # compress
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## ความซับซ้อน

- **find / union:** O(α(n)) ≈ O(1) amortized **พื้นที่:** O(n)

## การใช้งาน

- **Kruskaลs MST** — การตรวจจับวัฏจักรขณะเพิ่มขอบ
- **ส่วนประกอบที่เชื่อมต่อ** / การเชื่อมต่อแบบไดนามิก
- **การตรวจจับวัฏจักร** ในกราฟที่ไม่มีทิศทาง
- **Percolation** การแบ่งส่วนภาพ การรวมบัญชี/เครือข่าย

## ความเสี่ยง

โดยไม่มี path compression และ union by rank ต้นไม้จะเสื่อมลงเป็นห่วงโซ่ O(n) ไม่รองรับการ *แยก* เซตอย่างมีประสิทธิภาพ

## เหตุใดจึงสำคัญ

Union-find ตอบคำถาม "สิ่งสองสิ่งนี้เชื่อมต่อกันหรือไม่?" ในขนาดขนาดใหญ่มหาศาล ด้วยต้นทุนเกือบไม่มี

มันเป็นเครื่องยนต์ภายใน Kruskaลs MST และอัลกอริธึมกราฟและการจัดกลุ่มจำนวนมาก

การปรับปรุงสองแบบของมันเป็นบทเรียนที่น่าจดจำเกี่ยวกับวิธีการเล็ก ๆ ของโครงสร้างให้ประสิทธิภาพเกือบคงเวลา