Disjoint set union (union-find)

১ · সমস্যা — বন্যার পর কোন গ্রাম কোন গ্রামের সাথে যুক্ত?

সিলেটের একটি উপজেলায় বড় বন্যা হয়েছে। পানি নামার পর দেখা গেল সব রাস্তা ভেঙে গেছে, আটটি গ্রাম একে অন্যের থেকে বিচ্ছিন্ন। উপজেলা অফিস একটি একটি করে রাস্তা মেরামত করছে, আর প্রতিদিন খবর আসছে “আজ ২ নম্বর আর ৩ নম্বর গ্রামের মধ্যের রাস্তা খুলেছে”. এর মধ্যেই ত্রাণের গাড়ির চালক জানতে চান: “আমি কি ০ নম্বর গ্রাম থেকে ৬ নম্বর গ্রামে যেতে পারব — সরাসরি রাস্তা না থাকলেও অন্য গ্রাম ঘুরে?”

এখানে দুই ধরনের ঘটনা মিশে আসছে: নতুন সংযোগ (রাস্তা খুলল) আর প্রশ্ন (দুটি গ্রাম কি যুক্ত?). পর্ব ৩৯-এর ভাষায় গ্রামগুলো একটি graph-এর vertex, রাস্তাগুলো edge. যে গ্রামগুলোর মধ্যে কোনো না কোনো পথে যাওয়া যায়, তারা মিলে একটি connected component. সংযোগ বাড়তে থাকা অবস্থায় এই প্রশ্নের উত্তর দেওয়ার সমস্যাটির নাম dynamic connectivity.

প্রতিটি প্রশ্নে নতুন করে BFS বা DFS চালানো যায় (পর্ব ৪০–৪১) — কিন্তু তাতে প্রতি প্রশ্নে O(n + m) সময়, যেখানে n গ্রাম আর m রাস্তা। দশ লাখ গ্রাম আর দশ লাখ প্রশ্নে সেটি প্রায় 10¹² ধাপ — অচল। আমাদের দরকার এমন একটি ডেটা স্ট্রাকচার, যা প্রতিটি নতুন রাস্তা আর প্রতিটি প্রশ্নকে প্রায় ধ্রুবক সময়ে সামলায়। সেটিই disjoint set union (DSU), যার আরেক নাম union-find.

একই কাঠামো আরও অনেক জায়গায় লুকিয়ে আছে। ফেসবুকে “বন্ধুর বন্ধু” ধরে যারা যুক্ত, তারা একটি friend circle — নতুন বন্ধুত্ব হলে দুটি circle মিশে যায়। একটি অফিসের কম্পিউটার নেটওয়ার্কে কোন কোন মেশিন কেবল দিয়ে একে অন্যের কাছে পৌঁছাতে পারে, সেটিও একই প্রশ্ন। সব ক্ষেত্রে মূল কথা দুটি: উপাদানগুলো কয়েকটি আলাদা, পরস্পর-বিচ্ছিন্ন (disjoint) দলে ভাগ — কেউ একসাথে দুই দলে নেই; আর দলগুলো সময়ের সাথে শুধু জোড়া লাগে.

তিনটি কাজ — DSU-এর ADT

প্রতিনিধির ধারণাটি সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ। DSU কোনো দলের সব সদস্যের তালিকা দিতে বাধ্য নয়; সে শুধু প্রতিটি দলের জন্য একজন নির্দিষ্ট সদস্যকে প্রতিনিধি রাখে। একই দলের যেকোনো দুজনকে find জিজ্ঞেস করলে একই উত্তর আসবে — যতক্ষণ মাঝে কোনো union না হয়। কে প্রতিনিধি, তা union-এর পর বদলাতে পারে; তাই find-এর উত্তর মনে রেখে পরে ব্যবহার করা ভুল।

গণিতের ভাষায়, “একই দলে আছে” সম্পর্কটি একটি equivalence relation: প্রত্যেকে নিজের সাথে একই দলে (reflexive), a যদি b-র দলে থাকে তো b-ও a-র দলে (symmetric), আর a~b ও b~c হলে a~c (transitive). যেকোনো equivalence relation উপাদানগুলোকে পরস্পর-বিচ্ছিন্ন শ্রেণিতে ভাগ করে — DSU সেই ভাগাভাগিকে ধাপে ধাপে মোটা করতে থাকে। এটিও একটি abstract data type: কাজগুলো ঠিক, কিন্তু ভেতরে কীভাবে রাখা হবে তা খোলা। পরের অংশগুলোতে আমরা চারটি বাস্তবায়ন দেখব, প্রতিটি আগেরটির দুর্বলতা সারিয়ে।

২ · প্রথম চেষ্টা — লেবেলের অ্যারে আর linked list

লেবেলের অ্যারে (quick-find)

সবচেয়ে সরল উপায়: একটি অ্যারে id[x] রাখুন, যাতে লেখা থাকে x কোন দলের। শুরুতে id[x] = x. তখন find(x) মানে শুধু id[x] পড়া — O(1). কিন্তু union(a, b)-তে a-র দলের সবার লেবেল বদলে b-র দলের লেবেল করতে হবে, আর কারা a-র দলে তা জানতে পুরো অ্যারে দেখতে হয় — O(n). এই পদ্ধতির নাম quick-find: খোঁজা দ্রুত, জোড়া ধীর। n টি গ্রামকে একটি দলে আনতে n − 1 টি union লাগে, তাই মোট Θ(n²) — দশ লাখ গ্রামে 10¹², আবার সেই অচল অবস্থা।

Pseudocode — quick-find (0-based)

find(x):     return id[x]                        // O(1)
union(a, b): A = id[a];  B = id[b]
             if A == B: return
             for i = 0 to n-1:                   // O(n): scan everyone
                 if id[i] == A: id[i] = B

Linked list আর weighted union — প্রথম চতুর বুদ্ধি

পুরো অ্যারে না ঘুরে শুধু a-র দলের সদস্যদের ছুঁতে চাইলে প্রতিটি দলকে একটি linked list হিসেবে রাখুন (পর্ব ১২): প্রতিটি node-এ একটি pointer থাকে list-এর মাথার (head) দিকে, আর head-ই প্রতিনিধি। find(x) = x-এর head pointer — O(1). union-এ একটি list আরেকটির শেষে জুড়ে দিতে হয়, আর জুড়ে দেওয়া list-এর প্রত্যেক সদস্যের head pointer বদলাতে হয়। খারাপ ক্রমে (প্রতিবার বড় list-টিকে ছোটটির পেছনে জোড়া) এটিও মোট Θ(n²).

সমাধান এক লাইনের: সবসময় ছোট list-টিকে বড়টির পেছনে জুড়ুন, যাতে head pointer বদলাতে হয় কম সদস্যের। একে বলে weighted union. ফলটি বিস্ময়কর, আর যুক্তিটি এই পর্বের মূল যুক্তির বীজ। একটি নির্দিষ্ট উপাদান x-কে দেখুন। x-এর head pointer বদলায় শুধু তখন, যখন x-এর list ছিল ছোটটি (বা সমান) — আর জোড়ার পর নতুন list-এর আকার অন্তত x-এর আগের list-এর দ্বিগুণ. শুরুতে আকার ১; প্রতিবার বদলে অন্তত দ্বিগুণ; আকার কখনো n ছাড়াতে পারে না। তাই x-এর pointer সর্বোচ্চ ⌊log₂ n⌋ বার বদলায়। n টি উপাদান মিলে সব union-এর মোট কাজ O(n log n), আর m টি find আর union মিলিয়ে মোট O(m + n log n). প্রতিটি উপাদানের হিসাবে এটি O(log n) — amortized: কোনো একটি union একাই n/2 টি pointer বদলাতে পারে, কিন্তু সব মিলিয়ে গড় খরচ ছোট।

Weighted union-এর “ছোটকে বড়র সাথে জুড়ুন” কৌশলটি কনটেস্টে small-to-large নামে আলাদা পরিচয় পেয়েছে — দুটি set বা map জোড়ার সময় সবসময় ছোটটির উপাদান বড়টিতে ঢোকালে প্রতিটি উপাদান সর্বোচ্চ log n বার সরে। কিন্তু DSU-এর জন্য আমরা আরও ভালো করতে পারি: union-এ কারও pointer বদলানোর দরকারই নেই, যদি পুরো list-এর বদলে শুধু একটি pointer বদলাই।

৩ · Forest — প্রত্যেকের হাতে শুধু parent-এর ঠিকানা

১৯৬৪ সালে Bernard Galler আর Michael Fischer যে ধারণা প্রকাশ করেন, তা আজও DSU-এর ভিত্তি: প্রতিটি দলকে একটি tree হিসেবে রাখুন, যেখানে প্রতিটি node শুধু তার parent-কে চেনে — সন্তানদের নয়। Tree-র root নিজেই নিজের parent, আর সে-ই দলের প্রতিনিধি। সব দল মিলে কয়েকটি tree-র একটি forest. পুরো forest রাখতে একটিই অ্যারে লাগে: parent pointer p[x].

Pseudocode — parent-pointer forest, no balancing yet (0-based)

makeSet(x):  p[x] = x                     // a root is its own parent
find(x):     while p[x] != x:  x = p[x]   // walk up to the root
             return x
union(a, b): ra = find(a);  rb = find(b)
             if ra != rb:  p[ra] = rb     // hang a's root under b's root

এখন union মাত্র একটি অ্যাসাইনমেন্ট (দুটি find বাদে)। কিন্তু find-এর খরচ নির্ভর করে tree কতটা উঁচু তার ওপর — আর union কোন root-কে কার নিচে বসাচ্ছে, তা নিয়ে আমরা কোনো নিয়ম রাখিনি। খারাপ ক্রমে কী হয়, দেখুন। পাঁচটি গ্রাম, আর প্রতিটি রাস্তা ০ নম্বর গ্রাম থেকে:

এই সরল forest-কে কখনো quick-union বলা হয়: union সস্তা, কিন্তু find-এর worst case O(n), কারণ tree-র উচ্চতা n − 1 পর্যন্ত যেতে পারে। পরের দুটি অংশে দুটি স্বাধীন কৌশল দেখব — একটি উচ্চতা বাড়তেই দেয় না, অন্যটি বেড়ে যাওয়া উচ্চতা কমিয়ে দেয়।

৪ · Union by size আর union by rank — ছোট tree বড়টির নিচে

আগের ডায়াগ্রামে দোষ ছিল একটাই: বড় tree গিয়ে বসছিল ছোটটির নিচে, ফলে বড় tree-র সব node-এর গভীরতা এক করে বাড়ছিল। উল্টোটা করুন। প্রতিটি root-এ তার tree-র আকার sz[root] রাখুন, আর union-এ ছোট tree-র root-কে বড় tree-র root-এর নিচে বসান — linked list-এর weighted union-এর মতোই। এর নাম union by size. সমান হলে যেকোনো একটি; এই পর্বে নিয়ম: প্রথম argument-এর root parent হবে।

প্রমাণ — উচ্চতা কখনো ⌊log₂ n⌋ ছাড়ায় না

দাবি: union by size ব্যবহার করলে যেকোনো node x-এর গভীরতা d হলে x-এর দলে অন্তত 2^d টি সদস্য আছে। যেহেতু কোনো দলে n-এর বেশি সদস্য থাকতে পারে না, 2^d ≤ n, অর্থাৎ d ≤ log₂ n — তাই প্রতিটি tree-র উচ্চতা ≤ ⌊log₂ n⌋.

যুক্তি: x-এর গভীরতা কখন বাড়ে? find বা union কোনো node-এর parent বদলায় না, শুধু union একটি root-এর parent বদলায়। তাই x-এর গভীরতা এক বাড়ে কেবল তখন, যখন x-এর tree-র root r অন্য একটি root s-এর নিচে বসে — আর নিয়ম অনুযায়ী তখন sz[r] ≤ sz[s]. জোড়ার পর x-এর দলের আকার sz[r] + sz[s] ≥ 2·sz[r]: অন্তত দ্বিগুণ। শুরুতে গভীরতা ০, দলের আকার ১ = 2⁰. প্রতিবার গভীরতা এক বাড়লে আকার অন্তত দ্বিগুণ হয়, আর গভীরতা না বাড়লেও আকার কমে না। Induction-এ, গভীরতা d হলে আকার ≥ 2^d. ∎ ওপরের ডায়াগ্রামে node 7-এর সারিটি ঠিক এই যুক্তিই দেখায়: 0/1 → 2/4 → 3/8.

ফল: find আর union দুটোই O(log n) worst case, প্রতিটি; বাড়তি জায়গা Θ(n) (দুটি অ্যারে p আর sz). সীমাটি নিখুঁত: ডায়াগ্রামের মতো “সমান আকারের দুটি দল বারবার জোড়া” দিলে n = 2^k-এ উচ্চতা ঠিক k হয় — এই tree-গুলোকে binomial tree বলে।

Union by rank — আকারের বদলে উচ্চতার একটি সীমা

অনেক বই (CLRS সহ) আকারের বদলে প্রতিটি root-এ একটি rank রাখে: শুরুতে ০; দুই root জোড়ার সময় কম rank-এর root যায় বেশি rank-এর নিচে; rank সমান হলে যেকোনো একটি নিচে যায় আর ওপরেরটির rank এক বাড়ে। এটিই union by rank. Path compression না থাকলে rank ঠিক tree-র উচ্চতা; থাকলে rank শুধু উচ্চতার একটি ওপরের সীমা (compression উচ্চতা কমায়, কিন্তু rank-কে কেউ কমায় না — দরকারও নেই)।

প্রমাণ (rank সংস্করণ): rank r-এর প্রতিটি root-এর tree-তে অন্তত 2^r টি node. r = 0-তে ১টি node, সত্য। rank r + 1 হয় কেবল তখন, যখন rank r-এর দুটি root জোড়া লাগে — দুই পাশে অন্তত 2^r করে, মোট অন্তত 2^r+1. অন্য union-এ বড় rank-এর root-এর rank বদলায় না, শুধু node বাড়ে। তাই rank ≤ log₂ n, আর উচ্চতা ≤ rank ≤ ⌊log₂ n⌋. ∎ বাড়তি সুবিধা: rank এত ছোট (৬৪-বিট মেশিনে ৬৪-এর কম) যে একটি byte-এই ধরে যায়।

৫ · Path compression — একবার খুঁজলে পরের বার শর্টকাট

দ্বিতীয় কৌশলটি আসে একটি অলস কিন্তু বুদ্ধিমান পর্যবেক্ষণ থেকে। find(x) যখন x থেকে root পর্যন্ত হাঁটে, পথের প্রতিটি node-এর root কে, তা আমরা জেনেই ফেলি। তাহলে ফেরার পথে প্রত্যেককে সরাসরি root-এর সাথে জুড়ে দিই না কেন? পরের বার তাদের কেউ find করলে এক লাফেই root. এটিই path compression. উপমায়: একজন নতুন কর্মী একবার কষ্ট করে জেনে নিলেন বিভাগীয় প্রধান কে; এরপর তিনি আর মাঝের সুপারভাইজারদের জিজ্ঞেস করেন না, সরাসরি প্রধানের কাছে যান — আর পথে যাঁদের জিজ্ঞেস করেছিলেন, তাঁরাও এখন প্রধানকে সরাসরি চেনেন।

Pseudocode — find with path compression (0-based)

find(x):                                  // recursive version
    if p[x] != x:  p[x] = find(p[x])      // point straight at the root
    return p[x]

find(x):                                  // iterative, two passes
    r = x
    while p[r] != r:  r = p[r]            // pass 1: locate the root
    while p[x] != r:  next = p[x];  p[x] = r;  x = next   // pass 2: re-link

আগের ডায়াগ্রামের শেষ tree নিন (উচ্চতা ৩), আর পরপর find(7), find(5), find(3) চালান:

দুটি খুঁটিনাটি লক্ষ করুন। প্রথমত, path compression শুধু find-এর পথের node-গুলোর parent বদলায়; কারও দল বদলায় না, তাই DSU-এর উত্তর একই থাকে। দ্বিতীয়ত, compression rank বা size-কে নষ্ট করে না: root-এর sz সঠিকই থাকে (দলের সদস্য-সংখ্যা বদলায়নি), শুধু rank আর “ঠিক উচ্চতা” থাকে না, থাকে উচ্চতার একটি ওপরের সীমা।

Path halving আর path splitting — এক পাসের বিকল্প

Recursive find সুন্দর, কিন্তু খুব লম্বা পথে recursion-এর গভীরতা বাড়ে, আর দুই-পাসের লুপ লিখতে একটু বেশি কোড। Tarjan আর van Leeuwen (১৯৮৪) দেখান যে দুটি এক-পাসের সরল রূপও একই O(α(n)) সীমা দেয়:

• Path halving: হাঁটার সময় প্রতি দ্বিতীয় node-কে তার দাদার (grandparent) সাথে জুড়ুন, আর সরাসরি দাদার কাছে লাফ দিন: p[x] = p[p[x]]; x = p[x];
• Path splitting: পথের প্রত্যেক node-কে তার দাদার সাথে জুড়ুন, কিন্তু হাঁটুন এক ধাপ করে।

পুরো কোড — গ্রামের রাস্তা আর প্রশ্ন

এবার অংশ ১-এর গল্পটি কোডে। আটটি গ্রাম; একটি তালিকায় রাস্তা খোলার খবর ("a b"), প্রশ্ন ("? a b") আর মাঝে মাঝে parent অ্যারে দেখার নির্দেশ ("show"). DSU-তে union by size আর path compression দুটোই আছে, আর একটি counter রাখে এখন কয়টি দল (component). C++-এ union একটি সংরক্ষিত শব্দ, তাই ফাংশনের নাম unite.

#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct DSU {
    vector<int> p, sz; int comps;
    DSU(int n) : p(n), sz(n, 1), comps(n) { iota(p.begin(), p.end(), 0); }   // make-set
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }           // path compression
    bool unite(int a, int b) {                                              // union by size
        a = find(a); b = find(b);
        if (a == b) return false;           // already connected: this road closes a cycle
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b]; --comps; return true;
    }
};
int main() {
    DSU d(8);
    vector<string> events = {"0 1", "2 3", "1 3", "show", "4 5", "6 7", "5 7", "0 2", "show",
                             "? 0 3", "? 2 6", "3 6", "? 2 6", "show"};
    for (const string& e : events) {
        if (e == "show") {
            cout << "parent:"; for (int x : d.p) cout << ' ' << x;
            cout << " | components = " << d.comps << '\n';
        } else if (e[0] == '?') {
            int a = e[2] - '0', b = e[4] - '0';
            cout << "query " << a << '-' << b << ": " << (d.find(a) == d.find(b) ? "yes" : "no") << '\n';
        } else {
            int a = e[0] - '0', b = e[2] - '0';
            cout << "road " << a << '-' << b << ": " << (d.unite(a, b) ? "joined" : "already connected (cycle)") << '\n';
        }
    }
}

road 0-1: joined
road 2-3: joined
road 1-3: joined
parent: 0 0 0 2 4 5 6 7 | components = 5
road 4-5: joined
road 6-7: joined
road 5-7: joined
road 0-2: already connected (cycle)
parent: 0 0 0 2 4 4 4 6 | components = 2
query 0-3: yes
query 2-6: no
road 3-6: joined
query 2-6: yes
parent: 0 0 0 0 0 4 0 6 | components = 1

class DSU:
    def __init__(self, n):
        self.p = list(range(n))           # make-set for every village
        self.sz = [1] * n
        self.comps = n
    def find(self, x):                    # path compression, two passes
        r = x
        while self.p[r] != r:
            r = self.p[r]
        while self.p[x] != r:
            self.p[x], x = r, self.p[x]
        return r
    def union(self, a, b):                # union by size
        a, b = self.find(a), self.find(b)
        if a == b:
            return False                  # already connected: this road closes a cycle
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.p[b] = a
        self.sz[a] += self.sz[b]
        self.comps -= 1
        return True

d = DSU(8)
events = ["0 1", "2 3", "1 3", "show", "4 5", "6 7", "5 7", "0 2", "show",
          "? 0 3", "? 2 6", "3 6", "? 2 6", "show"]
for e in events:
    if e == "show":
        print("parent:", *d.p, "| components =", d.comps)
    elif e[0] == "?":
        _, a, b = e.split()
        print(f"query {a}-{b}:", "yes" if d.find(int(a)) == d.find(int(b)) else "no")
    else:
        a, b = map(int, e.split())
        print(f"road {a}-{b}:", "joined" if d.union(a, b) else "already connected (cycle)")

road 0-1: joined
road 2-3: joined
road 1-3: joined
parent: 0 0 0 2 4 5 6 7 | components = 5
road 4-5: joined
road 6-7: joined
road 5-7: joined
road 0-2: already connected (cycle)
parent: 0 0 0 2 4 4 4 6 | components = 2
query 0-3: yes
query 2-6: no
road 3-6: joined
query 2-6: yes
parent: 0 0 0 0 0 4 0 6 | components = 1

৬ · O(α(n)) — প্রায় ধ্রুবক, কিন্তু ঠিক ধ্রুবক নয়

শুধু union by size: প্রতিটি কাজ O(log n). শুধু path compression (কোনো balancing ছাড়া): m টি কাজে মোট O(m log n)-এর মতো — একটি একক find O(n) হতে পারে, কিন্তু গড়ে log. দুটো একসাথে দিলে? ১৯৭৩ সালে John Hopcroft আর Jeffrey Ullman প্রমাণ করেন O(log* n) প্রতি কাজে, যেখানে log* n (iterated logarithm) মানে n-কে কতবার log₂ করলে ১-এর নিচে বা সমান নামে। log* 2⁶⁵⁵³⁶ = 5 — এটিই ইতিমধ্যে অবিশ্বাস্য ধীরে বাড়া একটি ফাংশন।

১৯৭৫ সালে Robert Tarjan আরও নিখুঁত উত্তর দেন: m টি কাজে (যার মধ্যে n টি make-set) মোট সময় O(m α(n)), আর এই বিশ্লেষণ ঠিক — শক্ত (tight). এখানে α হলো inverse Ackermann ফাংশন। Ackermann ফাংশন A (Wilhelm Ackermann, ১৯২৮) এত দ্রুত বাড়ে যে exponential, tower — কোনো পরিচিত ফাংশন তার সাথে পাল্লা দিতে পারে না। α(n) হলো তার উল্টো: “কোন ছোট k-তে A-এর মান n ছাড়ায়?”

কতটা ধীরে বাড়ে, তা অনুভব করতে CLRS-এর সংজ্ঞাটি দেখুন। A₀(j) = j + 1, আর A_k(j) মানে A_k−1-কে j + 1 বার পরপর প্রয়োগ। তাহলে A₁(1) = 3, A₂(1) = 7, A₃(1) = 2047, আর A₄(1) এমন একটি সংখ্যা যা 2²⁰⁴⁸-এরও অনেক অনেক গুণ বড় — 10⁸⁰-কে বামন করে দেয়। α(n) = সবচেয়ে ছোট k, যাতে A_k(1) ≥ n. তাই n ≤ 2047 হলে α(n) ≤ 3, আর বাস্তবে কখনো দেখা যাবে এমন যেকোনো n-এ α(n) ≤ 4. (বিভিন্ন বইয়ে সংজ্ঞা সামান্য আলাদা, কিন্তু সবখানেই α “বাস্তবে ছোট ধ্রুবক”।)

তাহলে কেন O(1) বলা হয় না? কারণ গাণিতিকভাবে α(n) অসীমের দিকে যায় — খুব খুব ধীরে, কিন্তু যায়। আর এটি শুধু বিশ্লেষণের দুর্বলতা নয়: Tarjan ১৯৭৯ সালে একটি নির্দিষ্ট মডেলে (pointer machine) প্রমাণ করেন যে এর চেয়ে ভালো সম্ভব নয়, আর Michael Fredman ও Michael Saks ১৯৮৯ সালে cell probe মডেলে দেখান যে যেকোনো union-find ডেটা স্ট্রাকচারকে amortized Ω(α(n)) দিতেই হবে। অর্থাৎ এই সরল দশ লাইনের কোডটি তাত্ত্বিকভাবে সর্বোত্তম।

৭ · প্রয়োগ — Kruskal থেকে ছবির অংশ চেনা পর্যন্ত

Kruskal-এর minimum spanning tree

DSU-এর সবচেয়ে বিখ্যাত ব্যবহার। ধরুন আটটি গ্রামকে বিদ্যুতের লাইনে জুড়তে হবে, প্রতিটি সম্ভাব্য লাইনের খরচ জানা, আর সবচেয়ে কম খরচে সব গ্রাম যুক্ত করতে হবে — এটিই minimum spanning tree (MST). Kruskal-এর অ্যালগরিদম (Joseph Kruskal, ১৯৫৬): সব edge খরচ অনুযায়ী সাজান, তারপর সস্তা থেকে দামি ক্রমে প্রতিটি edge নিন — যদি তার দুই প্রান্ত এখনো আলাদা component-এ থাকে। একই component-এ থাকলে সেই edge একটি cycle বানাত, তাই বাদ। “এখনো আলাদা কি না” — ঠিক DSU-এর প্রশ্ন।

// Kruskal: edges as (weight, u, v); DSU from the code above
sort(edges.begin(), edges.end());              // O(E log E)
DSU d(n); long long total = 0; int used = 0;
for (auto [w, u, v] : edges)
    if (d.unite(u, v)) { total += w; ++used; } // keep the edge only if it joins two components
// used == n - 1 means the graph was connected; total = MST weight

সময় O(E log E) সর্টের জন্য, আর DSU-এর অংশ মাত্র O(E α(V)) — সর্টই বাধা। কেন এই greedy ঠিক (cut property), তা প্রমাণসহ পর্ব ৪৫-এ।

Connected component গোনা আর undirected গ্রাফে cycle ধরা

দুটি কাজই ওপরের কোডে আছে। Component-এর সংখ্যা = n − (সফল union-এর সংখ্যা), কারণ প্রতিটি সফল union দুটি দলকে এক করে। আর একটি undirected graph-এর edge একে একে নেওয়ার সময় যদি কোনো edge (u, v)-তে find(u) == find(v) হয়, তাহলে u আর v-এর মধ্যে আগেই একটি পথ ছিল — নতুন edge সেই পথের সাথে মিলে একটি cycle বানায়। এই cycle detection O(E α(V))-এ চলে, আর একই সাথে বলে দেয় কোন edge-টি প্রথম cycle বানাল। সতর্কতা: এটি শুধু undirected গ্রাফে কাজ করে; directed গ্রাফে cycle খুঁজতে DFS-এর রং-পদ্ধতি লাগে (পর্ব ৪১–৪২), কারণ সেখানে “একই দলে” মানে cycle নয়।

Offline প্রশ্ন — সময়কে উল্টো দিকে চালানো

DSU দল ভাঙতে পারে না। কিন্তু সব প্রশ্ন যদি আগে থেকে জানা থাকে (offline), তাহলে একটি কৌশল আছে। ধরুন রাস্তাগুলো একে একে ভাঙছে, আর প্রতিটি ভাঙার পর জানতে চাই কয়টি component. ক্রমটি উল্টে দিন: শুরু করুন শেষ অবস্থা থেকে (যেসব রাস্তা কখনো ভাঙেনি, শুধু সেগুলো জুড়ে), তারপর ভাঙার উল্টো ক্রমে রাস্তাগুলো যোগ করুন। “ভাঙা” হয়ে গেল “জোড়া” — DSU-এর নিজের কাজ। উত্তরগুলো উল্টো ক্রমে জমা করে শেষে আবার উল্টে দিলেই হলো, মোট O((n + m) α(n)). একইভাবে, “শুধু w-এর চেয়ে কম ওজনের edge ব্যবহার করে u থেকে v যাওয়া যায়?” — প্রশ্নগুলো w অনুযায়ী আর edge-গুলো ওজন অনুযায়ী সাজিয়ে, দুই তালিকা একসাথে এগিয়ে, প্রতিটি প্রশ্নের আগে সব হালকা edge জুড়ে দিন। Tree-তে offline LCA-র Tarjan-এর পদ্ধতিও DSU দিয়ে চলে (পর্ব ৪৮)।

Percolation আর ছবির অংশ চিহ্নিত করা

একটি n × n গ্রিডের প্রতিটি ঘর p সম্ভাবনায় খোলা। ওপরের সারি থেকে খোলা ঘর ধরে নিচের সারিতে পৌঁছানো যায় কি? — এটি পদার্থবিজ্ঞানের percolation সমস্যা: পানি কি মাটির স্তর ভেদ করে চুইয়ে নামবে? DSU-তে প্রতিটি খোলা ঘরকে তার খোলা প্রতিবেশীর সাথে union করুন, আর দুটি কাল্পনিক node রাখুন — “ওপর” (ওপরের সারির সব খোলা ঘর এর সাথে যুক্ত) আর “নিচ”. find(ওপর) == find(নিচ) হলেই চুইয়ে নামে। এলোমেলো ঘর একে একে খুলে কখন প্রথম চুইয়ে নামে তা দেখার Monte Carlo পরীক্ষায় বর্গ গ্রিডে সেই সীমা প্রায় p ≈ 0.5927.

ছবিতেও একই কাজ: একটি সাদা-কালো ছবিতে পাশাপাশি থাকা কালো pixel-গুলো মিলে কয়টি আলাদা বস্তু? — connected component labeling. প্রচলিত দুই-পাস পদ্ধতিতে প্রথম পাসে প্রতিটি pixel-কে বাঁ আর ওপরের প্রতিবেশীর লেবেল দেওয়া হয়; দুই লেবেল মুখোমুখি হলে তাদের union. দ্বিতীয় পাসে প্রতিটি লেবেলকে তার find দিয়ে বদলে দেওয়া হয়। ১০ লাখ pixel-এর ছবিতে এটি প্রায় রৈখিক সময়ে চলে — OCR-এ অক্ষর আলাদা করা, মেডিক্যাল ছবিতে কোষ গোনা বা স্যাটেলাইট ছবিতে বন্যার পানির এলাকা মাপায় এই কৌশল ব্যবহার হয়।

প্রতিটি দলের সাথে বাড়তি তথ্য

Root-ই দলের প্রতিনিধি, তাই দলের যেকোনো সমষ্টিগত তথ্য — সদস্য-সংখ্যা, মোট টাকা, সবচেয়ে ছোট মান — শুধু root-এ রাখলেই চলে, আর union-এ দুই root-এর তথ্য জুড়ে দিলেই হলো। ধরুন প্রতিটি গ্রামে কিছু ত্রাণের প্যাকেট আছে: sum[root]-এ দলের মোট প্যাকেট রাখুন; union-এ sum[a] += sum[b]; প্রশ্ন “x-এর দলে মোট কত প্যাকেট?” = sum[find(x)]. sz অ্যারেটি আসলে এরই একটি উদাহরণ। শর্ত একটাই: তথ্যটিকে “জোড়া” যেতে হবে (যোগ, min, max, gcd — হ্যাঁ; median — সহজে নয়)। আর মনে রাখুন, non-root node-এর এই ঘরগুলো পুরোনো, অর্থহীন মান রাখতে পারে — সবসময় find(x) দিয়ে পড়ুন।

৮ · Parity DSU — “শত্রুর শত্রু বন্ধু”

একটি কলেজের বিতর্ক উৎসবে পাঁচজন অংশগ্রহণকারীকে দুটি দলে ভাগ করতে হবে। আয়োজকের কাছে কিছু তথ্য আসছে: “0 আর 1 প্রতিপক্ষ (আলাদা দলে)”, “3 আর 4 একই দলে” — এমন। প্রতিটি নতুন তথ্যে প্রশ্ন: এ পর্যন্ত সব তথ্য কি একসাথে সত্য হতে পারে, নাকি কোথাও স্ববিরোধ (contradiction)? এখানে দলের ভেতরে আরেকটি তথ্য লাগে: শুধু “একই component-এ” নয়, “একই পক্ষে না উল্টো পক্ষে”.

Parity DSU-তে প্রতিটি node x একটি বাড়তি bit রাখে, par[x]: x তার parent-এর সাথে একই দলে (0) না উল্টো দলে (1). Root পর্যন্ত পথের সব bit-এর XOR = x আর root-এর সম্পর্ক। কেন XOR? “শত্রুর শত্রু বন্ধু”: উল্টো ⊕ উল্টো = একই, ঠিক 1 ⊕ 1 = 0. find(x) এখন দুটি জিনিস ফেরত দেয় — root, আর x-এর parity root-এর সাপেক্ষে; path compression-এর সময় parity-ও জমা হয়ে নতুন parent (root)-এর সাপেক্ষে হয়ে যায়।

• নতুন তথ্য (a, b, d), যেখানে d = 1 মানে প্রতিপক্ষ, 0 মানে একই দল। find(a) = (ra, pa), find(b) = (rb, pb).
• ra ≠ rb: দুই দল এখনো সম্পর্কহীন — জুড়ে দিন। rb-কে ra-এর নিচে বসালে চাই pa ⊕ par[rb] ⊕ pb = d, তাই par[rb] = pa ^ pb ^ d.
• ra == rb: সম্পর্ক আগেই নির্ধারিত, pa ⊕ pb. সেটি d-এর সমান হলে সামঞ্জস্যপূর্ণ, না হলে স্ববিরোধ.

#include <cstdio>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
vector<int> p, par, sz;            // par[x] = 1: x is on the other team from p[x]
pair<int, int> findp(int x) {      // (root, parity of x relative to the root)
    if (p[x] == x) return {x, 0};
    auto [r, q] = findp(p[x]);
    par[x] ^= q; p[x] = r;         // path compression keeps the parity to the root
    return {r, par[x]};
}
int main() {
    int n = 5;
    p.resize(n); par.assign(n, 0); sz.assign(n, 1);
    for (int i = 0; i < n; ++i) p[i] = i;
    vector<tuple<int, int, int>> claims = {{0, 1, 1}, {1, 2, 1}, {0, 2, 0}, {2, 3, 1}, {3, 4, 0}, {4, 1, 1}};
    for (auto [a, b, d] : claims) {            // d = 1: enemies, d = 0: same team
        auto [ra, pa] = findp(a);
        auto [rb, pb] = findp(b);
        const char* word = d ? "enemies" : "friends";
        if (ra == rb) {
            bool ok = (pa ^ pb) == d;
            printf("%d %d %s: already implied, %s\n", a, b, word, ok ? "consistent" : "CONTRADICTION");
            if (!ok) break;
        } else {
            if (sz[ra] < sz[rb]) swap(ra, rb);   // union by size; the parity formula is symmetric
            p[rb] = ra; par[rb] = pa ^ pb ^ d; sz[ra] += sz[rb];
            printf("%d %d %s: recorded\n", a, b, word);
        }
    }
    printf("parent:"); for (int x : p) printf(" %d", x);
    printf(" | parity:"); for (int x : par) printf(" %d", x);
    printf("\n");
}

0 1 enemies: recorded
1 2 enemies: recorded
0 2 friends: already implied, consistent
2 3 enemies: recorded
3 4 friends: recorded
4 1 enemies: already implied, CONTRADICTION
parent: 0 0 0 0 0 | parity: 0 1 0 1 1

n = 5
p, par, sz = list(range(n)), [0] * n, [1] * n   # par[x] = 1: x is on the other team from p[x]

def find(x):                       # returns (root, parity of x relative to the root)
    if p[x] == x:
        return x, 0
    r, q = find(p[x])
    par[x] ^= q                    # path compression keeps the parity to the root
    p[x] = r
    return r, par[x]

claims = [(0, 1, 1), (1, 2, 1), (0, 2, 0), (2, 3, 1), (3, 4, 0), (4, 1, 1)]
for a, b, d in claims:             # d = 1: enemies, d = 0: same team
    (ra, pa), (rb, pb) = find(a), find(b)
    word = "enemies" if d else "friends"
    if ra == rb:
        ok = (pa ^ pb) == d
        print(f"{a} {b} {word}: already implied, {'consistent' if ok else 'CONTRADICTION'}")
        if not ok:
            break
    else:
        if sz[ra] < sz[rb]:        # union by size; the parity formula is symmetric
            ra, rb = rb, ra
        p[rb], par[rb] = ra, pa ^ pb ^ d
        sz[ra] += sz[rb]
        print(f"{a} {b} {word}: recorded")
print("parent:", *p, "| parity:", *par)

0 1 enemies: recorded
1 2 enemies: recorded
0 2 friends: already implied, consistent
2 3 enemies: recorded
3 4 friends: recorded
4 1 enemies: already implied, CONTRADICTION
parent: 0 0 0 0 0 | parity: 0 1 0 1 1

এটি আসলে bipartite graph যাচাই: প্রতিটি “প্রতিপক্ষ” তথ্য একটি edge, আর প্রশ্ন হলো vertex-গুলোকে দুই রঙে রাঙানো যায় কি না, যাতে প্রতিটি edge-এর দুই প্রান্ত আলাদা রঙের। BFS দিয়েও করা যায় (পর্ব ৪০), কিন্তু edge যখন একে একে আসে আর প্রতিটির পর উত্তর চাই, তখন parity DSU সবচেয়ে সহজ। একই ধারণা আরও সাধারণ করা যায় — weighted DSU: par[x]-এর জায়গায় diff[x] = (x-এর মান) − (parent-এর মান) রাখুন, XOR-এর জায়গায় যোগ। তখন “A-র ওজন B-র চেয়ে ৩ কেজি বেশি” ধরনের তথ্য জমা করা আর স্ববিরোধ ধরা যায়। Mod 3 দিয়ে করলে “A খায় B-কে” ধাঁচের তিন-প্রজাতির খাদ্যশৃঙ্খলের একটি পরিচিত কনটেস্ট-সমস্যাও একই ছাঁচে পড়ে।

DSU যা পারে না

DSU-এর গতির দাম হলো সীমিত ক্ষমতা। (১) দল ভাঙা (split) বা edge মুছে ফেলা দক্ষভাবে সম্ভব নয় — parent pointer থেকে বোঝা যায় না কোন union কোন edge-এর জন্য হয়েছিল, আর path compression সেই ইতিহাসও মুছে দেয়। (২) একটি উপাদান মুছে ফেলা: প্রচলিত কৌশল হলো তাকে “মৃত” চিহ্ন দিয়ে আলাদা নতুন id-তে একা একটি দল খোলা, কিন্তু সেটি পুরোনো tree থেকে তাকে সত্যিই বের করে না। (৩) দলের সদস্যদের তালিকা: parent pointer শুধু ওপরে যায়, তাই সদস্য দেখাতে বাড়তি একটি circular linked list (প্রতি দলে “next” pointer, union-এ দুই চক্র জুড়ে দেওয়া, O(1)) রাখতে হয়। মুছে ফেলা আর জোড়া দুটোই লাগলে fully dynamic connectivity-এর জটিল স্ট্রাকচার লাগে, যেগুলো polylog সময় নেয়।

৯ · AI-এর যুগে DSU — দশ লাইনের কোড, এক লাইনের ভুল

“Union-find লিখে দাও” — যেকোনো AI সহকারী নিখুঁত দেখতে দশ লাইন দেবে। কিন্তু DSU-এর ভুল প্রায় কখনো compile error দেয় না, আর ছোট পরীক্ষায় উত্তরও প্রায়ই ঠিক আসে। ভুল লুকিয়ে থাকে এক লাইনে: union-এ root-এর বদলে সরাসরি p[a] = b, size হালনাগাদ ভুল root-এ, বা find-এর ফল ব্যবহার না করে পুরোনো p[x]-কে প্রতিনিধি ধরা। আর complexity-র প্রশ্নে AI প্রায়ই আত্মবিশ্বাসের সাথে “প্রতিটি কাজ O(1)” বলে, “amortized” আর “α” দুটোই বাদ দিয়ে।

DSU-এর কোডে AI সাধারণত যেসব ভুল করে

DSU-এর কোড যাচাইয়ের চেকলিস্ট

• union-এ দুই পাশেই find ডেকে root জুড়েছি; একই root হলে কিছু না করে false ফেরত দিচ্ছি
• প্রতিটি কাজের পর পরীক্ষা: সব root-এর size-এর যোগফল n, আর component-এর counter = root-এর সংখ্যা
• Edge case চালিয়েছি: n = 1, নিজের সাথে union(x, x), একই union দুবার, পুরো শিকল, সব এক দলে
• হাজারটি এলোমেলো union আর প্রশ্নে উত্তর মিলিয়েছি একটি brute force-এর সাথে (প্রতি প্রশ্নে BFS, বা quick-find) — stress testing
• Python-এ লম্বা শিকলে recursion-এর সীমা পরীক্ষা করেছি, দরকার হলে লুপ বা path halving দিয়েছি
• AI-এর complexity দাবিতে “amortized” আর “α(n)” আছে কি না দেখেছি, আর একক কাজের worst case আলাদা করে জিজ্ঞেস করেছি