Union-Find / Disjoint Set

समूह, trees के रूप में

Union-Find (Disjoint Set Union) हर समूह को एक tree के रूप में दिखाता है, जहाँ हर node एक parent की ओर इशारा करता है, और root अपना ही parent होता है। find(x), x का समूह पहचानने के लिए root तक जाता है; union(x, y) एक root को दूसरे के नीचे जोड़ता है।

Path compression + union by rank

दो optimizations इसे लगभग constant time बना देते हैं: path compression find के दौरान tree को चपटा करता है, और union by rank छोटे tree को बड़े के नीचे जोड़ता है।

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

Output:

uf = UnionFind(5)
uf.union(0, 1)
uf.find(0) == uf.find(1)  # True

कहाँ इस्तेमाल होता है

Undirected graph में cycle पहचानना, Kruskal's MST, connected components गिनना, और 'friend circles' जैसी समस्याएँ — सब Union-Find पर निर्भर करती हैं।

त्वरित जांच

Amortized complexity की समझ परखें।

त्वरित जाँच: Path compression और union by rank के साथ, find/union लगभग चलते हैं:

• O(n)
• O(log n)
• O(n log n)
• लगभग O(1) (inverse-Ackermann)