মডিউল ১০_৭ঃ Union by rank

আমরা Union by size দেখেছি। এখন আমরা union by rank বা union by level দেখবো।

এই পদ্ধতির মেইন ধারনাটা হচ্ছে দুইটা গ্রুপের union করার সময় যে গ্রুপের level বেশি সেই গ্রুপের আন্ডারে আরেকটা গ্রুপকে আনবো।

একটা উদাহরন এর মাধ্যমে বোঝার চেষ্টা করি।

ধরো তোমার কাছে দুইটা গ্রুপ আছে । এখন এখানে গ্রুপ ১ এর লেভেল ৩ আরেকটা গ্রুপের লেভেল হচ্ছে ২। তাহলে আমরা যদি ২ এর আন্ডারে ১ কে নেই তাহলে গ্রুপ ২ এর লেভেল হবে ৪।

আর যদি গ্রুপ ১ এর আন্ডারে গ্রুপ ২ কে নেই তাহলে লেভেল হবে ৩। লেভেল পরিবর্তন হবে না।

তার মানে যার গ্রুপের লেভেল বড় তাকেই যদি লিডার বানাই সেটাই বেশি অপ্টিমাইজ হবে।

তাহলে এখন প্রশ্ন আসতে পারে যদি লেভেল সমান হয়?

যদি লেভেল সমান হয় তাহলে যেকোনো গ্রুপের আন্ডারে আরেক গ্রুপকে আনলে যার আন্ডারে এনেছি তার লেভেল ১ বেড়ে যাবে।

তাহলে এভাবে লেভেল এর উপর ভিত্তি করেও আমরা union করতে পারি।

// Some code
void dsu_union_by_level(int node1, int node2)
{
    int leaderA = dsu_find(node1);
    int leaderB = dsu_find(node2);
    if (level[leaderA] > level[leaderB])
    {
        par[leaderB] = leaderA;
    }
    else if (level[leaderB] > level[leaderA])
    {
        par[leaderA] = leaderB;
    }
    else
    {
        par[leaderA] = leaderB;
        level[leaderB]++;
    }
}

কোড এ আমরা একটা লেভেল এ্যারে মেইনটেইন করব আর শুরুতে সবার লেভেল ০ থাকবে। এরপর আমরা দেখবো দুইটা নোড এর মধ্যে কার লেভেল বেশি। যার বেশি তার লিডারকে অন্য গ্রুপের লিডার এর প্যারেন্ট হিসেবে সেট করে দিব। যদি সমান হয় তাহলে যেকোনো একজনকে লিডার বানিয়ে ওই লিডার এর লেভেল সাইজ ১ বাড়িয়ে দিব।

সম্পূর্ণ কোডঃ

// Some code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int par[N];
int group_size[N];
int level[N];
void dsu_initialize(int n)
{
    for (int i = 0; i < n; i++)
    {
        par[i] = -1;
        group_size[i] = 1;
        level[i] = 0;
    }
}
int dsu_find(int node)
{
    if (par[node] == -1)
        return node;
    int leader = dsu_find(par[node]);
    par[node] = leader;
    return leader;
}
void dsu_union(int node1, int node2)
{
    // bad
    int leaderA = dsu_find(node1);
    int leaderB = dsu_find(node2);
    par[leaderA] = leaderB;
}
void dsu_union_by_level(int node1, int node2)
{
    int leaderA = dsu_find(node1);
    int leaderB = dsu_find(node2);
    if (level[leaderA] > level[leaderB])
    {
        par[leaderB] = leaderA;
    }
    else if (level[leaderB] > level[leaderA])
    {
        par[leaderA] = leaderB;
    }
    else
    {
        par[leaderA] = leaderB;
        level[leaderB]++;
    }
}
void dsu_union_by_size(int node1, int node2)
{
    int leaderA = dsu_find(node1);
    int leaderB = dsu_find(node2);
    if (group_size[leaderA] > group_size[leaderB])
    {
        par[leaderB] = leaderA;
        group_size[leaderA] += group_size[leaderB];
    }
    else
    {
        par[leaderA] = leaderB;
        group_size[leaderB] += group_size[leaderA];
    }
}
int main()
{
    dsu_initialize(7);
    dsu_union_by_level(1, 2);
    dsu_union_by_level(2, 3);
    dsu_union_by_level(4, 5);
    dsu_union_by_level(5, 6);
    dsu_union_by_level(1, 4);
    cout << dsu_find(1) << endl;
    cout << dsu_find(4) << endl;
    return 0;
}