Disjoint Set Union (Union-Find)

Disjoint Set Union (DSU) বা Union-Find একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা গেম থিওরি, গ্রাফ অ্যালগরিদম এবং নেটওয়ার্ক ইন্টার-কানেক্টিভিটি ইস্যুগুলিতে ব্যাপকভাবে ব্যবহৃত হয়। এটি মূলত দুটি অপারেশন সমর্থন করে:

1. Union: দুটি সেট (set) একত্রিত করা।
2. Find: কোন একটি উপাদান কোন সেটের অন্তর্ভুক্ত তা খুঁজে বের করা।

এই ডাটা স্ট্রাকচারটি সাধারণত Connected Components চিহ্নিত করতে, Cycle Detection এবং MST (Minimum Spanning Tree) নির্মাণের জন্য ব্যবহৃত হয়।

DSU / Union-Find এর মূল ধারণা

1. Union অপারেশন: দুটি সেট একত্রিত করা।
2. Find অপারেশন: কোন উপাদান কোন সেটে আছে তা খুঁজে বের করা।

Path Compression এবং Union by Rank হল দুটি অপ্টিমাইজেশন টেকনিক যা Union-Find এর কার্যকারিতা বৃদ্ধি করে:

• Path Compression: যখন একটি find অপারেশন করা হয়, তখন প্রতিটি নোডকে তার রুটের সরাসরি সন্তান বানিয়ে দেওয়া হয়। এতে পরবর্তীতে ওই নোড খুঁজে পাওয়া দ্রুত হয়।
• Union by Rank: যখন দুটি সেট একত্রিত করা হয়, তখন ছোট র্যাঙ্কের (হাইটের) সেটটি বড় র্যাঙ্কের সেটের নিচে যুক্ত করা হয়। এতে গাছের উচ্চতা কম থাকে, ফলে অপারেশনগুলো দ্রুত হয়।

Union-Find এর ইমপ্লিমেন্টেশন

১. Union-Find Data Structure Class

public class UnionFind {
    private int[] parent;
    private int[] rank;

    // কন্সট্রাক্টর
    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        
        // প্রতিটি এলিমেন্ট নিজেই একটি প্যারেন্ট
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;  // প্রাথমিকভাবে র্যাঙ্ক (হাইট) 0
        }
    }

    // Find অপারেশন: উপাদানটির মূল প্যারেন্ট খুঁজে পাওয়া
    public int find(int p) {
        if (parent[p] != p) {
            parent[p] = find(parent[p]);  // Path compression
        }
        return parent[p];
    }

    // Union অপারেশন: দুটি সেট একত্রিত করা
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        // যদি রুট প্যারেন্ট এক হয়ে যায়, তাহলে কোন কাজ করার প্রয়োজন নেই
        if (rootP == rootQ) return;

        // Union by rank: ছোট গাছকে বড় গাছের নিচে রাখা
        if (rank[rootP] > rank[rootQ]) {
            parent[rootQ] = rootP;
        } else if (rank[rootP] < rank[rootQ]) {
            parent[rootP] = rootQ;
        } else {
            parent[rootQ] = rootP;
            rank[rootP]++;  // র্যাঙ্ক বাড়ানো
        }
    }

    // Check যদি দুটি উপাদান একই সেটে থাকে
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}

২. Main Method Example

public class Main {
    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);  // ১০টি উপাদান (0-9)

        // বিভিন্ন ইউনিয়ন অপারেশন
        uf.union(1, 2);
        uf.union(2, 3);
        uf.union(4, 5);
        uf.union(6, 7);
        uf.union(8, 9);
        uf.union(1, 5);

        // উপাদানগুলি একই সেটে আছে কিনা চেক করা
        System.out.println(uf.connected(1, 3));  // true
        System.out.println(uf.connected(1, 4));  // true
        System.out.println(uf.connected(1, 9));  // false
    }
}

ব্যাখ্যা:

1. Find Operation: find(p) ফাংশন একটি উপাদান p এর মূল প্যারেন্ট খুঁজে বের করে, এবং path compression প্রযুক্তি ব্যবহার করে প্যারেন্ট লিঙ্কগুলো কমিয়ে দেয়, যাতে পরবর্তী find অপারেশনগুলো দ্রুত হয়।
2. Union Operation: union(p, q) দুটি উপাদান p এবং q এর জন্য তাদের রুট প্যারেন্ট খুঁজে বের করে, এবং যদি তারা আলাদা সেটে থাকে, তবে তাদের একটি করে একত্রিত করে। union by rank ব্যবহার করা হয় যাতে গাছের উচ্চতা কম থাকে।
3. Connected Operation: connected(p, q) চেক করে যে, p এবং q একই সেটে (একই রুট প্যারেন্টে) রয়েছে কি না।

আউটপুট:

true
true
false

সারাংশ

Union-Find বা Disjoint Set Union (DSU) একটি শক্তিশালী ডাটা স্ট্রাকচার যা বিশেষভাবে MST (Minimum Spanning Tree) অ্যালগরিদম, Cycle Detection এবং Network Connectivity সমস্যা সমাধানে ব্যবহৃত হয়। এই ডাটা স্ট্রাকচারটি দুটি প্রধান অপারেশন Union (এলিমেন্টগুলো একত্রিত করা) এবং Find (একটি উপাদান কোন সেটের অন্তর্ভুক্ত তা খুঁজে বের করা) এর জন্য ব্যবহার করা হয়।

অপটিমাইজেশন:

• Path Compression: find অপারেশনটি দ্রুত করার জন্য।
• Union by Rank: union অপারেশনটি দ্রুত করার জন্য, গাছের উচ্চতা কমানোর জন্য।

এই কৌশলটি Greedy Algorithm এবং Graph Theory এর বিভিন্ন সমস্যা সমাধানে ব্যাপকভাবে ব্যবহৃত হয়।