DSU กับการบีบอัดเส้นทาง

DSU คืออะไร

# Naive DSU without optimisations
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own parent

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

ปัญหาของการดำเนินการ find แบบพื้นฐาน

# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4]  => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4]  => find(0) takes 1 step

parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
    x = parent[x]
    steps += 1
print('Root:', x, 'Steps taken:', steps)

การบีบอัดเส้นทาง: แบบเวียนเกิดเที่ยวเดียว

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)

การบีบอัดเส้นทาง: แบบวนซ้ำสองเที่ยว

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]          # first pass: find root
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root             # second pass: compress
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False  # already connected

dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
    dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after  find(0):', dsu.parent[:])

ความซับซ้อนแบบเฉลี่ยตัดจำหน่ายของการบีบอัดเส้นทาง

# Demonstrating amortised benefit
import time

def build_chain(n):
    parent = list(range(n))
    for i in range(n - 1):
        parent[i] = i + 1  # chain: 0->1->2->...->n-1
    return parent

n = 1000
parent = build_chain(n)

# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
    root = parent[root]
# Compress
while parent[x] != root:
    nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0])  # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')

จำนวนองค์ประกอบที่เชื่อมต่อกัน

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        self.parent[px] = py
        self.components -= 1
        return True

dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
    dsu.union(u, v)
print('Components:', dsu.components)  # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')

DSU สำหรับปัญหากราฟ: จำนวนจังหวัด

def find_provinces(isConnected):
    n = len(isConnected)
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    count = n
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                if union(i, j):
                    count -= 1
    return count

matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix))  # 2: cities {0,1} and {2}

รูปแบบการบีบอัดเส้นทาง: การลดครึ่ง

class DSUHalving:
    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]]  # point to grandparent
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
    dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))

การตรวจสอบการเชื่อมต่อหลังการ union

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

    def connected(self, x, y):
        return self.find(x) == self.find(y)

dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7))   # True: 0-3-7
print(dsu.connected(0, 5))   # False: different components
print(dsu.connected(1, 5))   # True: 1-5

ข้อผิดพลาดที่พบบ่อยในการเขียน DSU

import sys
sys.setrecursionlimit(10000)  # needed for large recursive DSU

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        # Safe iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same component — do nothing
        self.parent[px] = py
        return True

dsu = DSU(5)
print(dsu.union(0, 1))  # True: merged
print(dsu.union(0, 1))  # False: already merged — no double-counting

การติดตามขนาดของ DSU

class DSUWithSize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            px, py = py, px           # attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]

    def get_size(self, x):
        return self.size[self.find(x)]

dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
    dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0))  # 3
print('Size of component containing 3:', dsu.get_size(3))  # 2
print('Size of component containing 5:', dsu.get_size(5))  # 1

ตรวจสอบความเข้าใจ

ทบทวนบทเรียน