মডিউল ১০_৩ঃ Find অপারেশন ইমপ্লিমেন্টেশন

এখন আমরা find অপারেশনটা ইমপ্লিমেন্ট করার চেষ্টা করব।

এটার জন্য আমরা কিছু নোড নিয়ে সেটার প্যারেন্ট এ্যারেটা একটু দেখিঃ

এখানে ধর আমরা ২ এর লিডারকে জানতে চাইলাম। তাহলে আমরা ২ কে জিজ্ঞেস করব ওর প্যারেন্ট কে। এই ক্ষেত্রে সেটা ১। আমরা ১ এর জাছে যাবো আর তাকে জিজ্ঞেস করবো তার প্যারেন্ট কে। এই ক্ষেত্রে সে বলবে ৩। তারপর ৩ এর কাছে গিয়ে জিজ্ঞেস করব তার প্যারেন্ট কে। ৩ বলবে সে নিজেই কেননা তার প্যারেন্ট -১। তাহলে আমরা বুঝে যাব ৩ হলো লিডার।

// Some code
int dsu_find(int node)
{
    if (par[node] == -1)
        return node;
    return dsu_find(par[node]);
}

উপরের ইমপ্লিমেন্টেশনের টাইম কমপ্লেক্সিটি O(N)|

এটাকে আরো অপ্টিমাইজ করে O(logn) করা সম্ভব। সেটি হচ্ছে আমরা যখন কোনো স্পেসিফিক নোড এর লিডার বের করব তখন সেইম গ্রুপের বাকি সকল এলিমেন্ট এর লিডার ও তাকে সেট করে দিব।

যেমনঃ উপরের এক্সাম্পল্টা যদি নেই তখন আমরা ১ এর লিডার ৩ পাওয়ার পর ২ এর লিডার ও ৩ সেট করে দিব প্যারেন্ট এ্যারেতে।

// Some code
int dsu_find(int node)
{
    if (par[node] == -1)
        return node;
    int leader = dsu_find(par[node]);
    par[node] = leader;
    return leader;
}