โครงสร้างดิสจอยต์-เซต (union-find) ที่มีการบีบอัดเส้นทางและการสหภาพตามอันดับคืออะไร?

Question

Accepted Answer

**ดิสจอยต์-เซต** (union-find) ติดตามองค์ประกอบที่ถูกแบ่งออกเป็นกลุ่มที่ไม่ทับซ้อนกัน และตอบคำถาม "**ทั้งสองอยู่ในกลุ่มเดียวกันหรือไม่?**" และ "**รวมสองกลุ่มเข้าด้วยกัน**" ใน **เวลาเกือบคงที่**। ด้วย **การบีบอัดเส้นทาง** และ **การสหภาพตามอันดับ** การดำเนินการทั้งสองจะทำงานใน **O(α(n))** — มีประสิทธิภาพ O(1) (α คือฟังก์ชัน Ackermann ผกผัน)।

## วิธีการทำงาน

แต่ละชุดคือต้นไม้; **ราก** คือตัวแทนของชุด `find` เดินไปยังราก; `union` เชื่อมต่อรากหนึ่งไว้ใต้อีกราก

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## โค้ด

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| การดำเนินการ | เวลา (ด้วยการปรับให้เหมาะสมทั้งสอง) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## การใช้งานทั่วไป

- **Kruskal MST** — รวมส่วนประกอบโดยไม่สร้างวงจร
- **ส่วนประกอบที่เชื่อมต่อ** ในกราฟหรือกริด
- **การเชื่อมต่อแบบไดนามิก** และปัญหาเครือข่าย/การซึมผ่าน

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

Union-find แก้ปัญหาการจัดกลุ่มและการเชื่อมต่อที่อาจต้องใช้การข้ามกราฟ O(n) ซ้ำ ๆ และลดให้เหลือเกือบ O(1) ต่อการสืบค้น

เป็นเครื่องมือที่จำเป็นเมื่อคุณต้องรวมชุดแบบค่อย ๆ และทดสอบการเชื่อมต่อ — หัวข้อสัมภาษณ์ระดับสูงที่พบบ่อย