গ্রাফপড়তে ৬ মিনিট লাগবে

ইউনিয়ন-ফাইন্ড (Union-Find বা DSU)

কে কার বন্ধু সেটুকুই শুধু মনে রাখা — আর চোখের পলকে তাদের এক গ্রুপে মিলিয়ে দেওয়া

find: O(α(n)) ≈ O(1)union: O(α(n)) ≈ O(1)space: O(n)

ভার্সিটির প্রথম দিনের কথা ভাবুন, যেখানে কোনো স্টুডেন্ট কাউকে চেনে না। এরপর ধীরে ধীরে তাদের মধ্যে বন্ধুত্ব হতে শুরু করলো এবং ফ্রেন্ড সার্কেল বা গ্রুপ তৈরি হলো। এখন যদি কেউ আপনাকে এসে হুট করে জিজ্ঞেস করে: "এই দুজন কি একই ফ্রেন্ড সার্কেলের?" অথবা বলে: "এই দুজনের ফ্রেন্ড সার্কেলকে মিলিয়ে দিন বা এক করে দিন।"

ঠিক এই কাজটাই করার জন্য যে জাদুকরী ডেটা স্ট্রাকচারটা আছে, তার নাম হলো ইউনিয়ন-ফাইন্ড (Union-Find) (অনেকে একে Disjoint Set Union বা DSU-ও বলে)। এটার একমাত্র কাজই হলো কোন জিনিসটা কোন গ্রুপে বা দলে আছে তার হিসাব রাখা এবং প্রায় O(1) বা চোখের পলকে তাদের নিয়ে নাড়াচাড়া করা।

আসল আইডিয়াটা কী?

প্রতিটা স্টুডেন্ট বা এলিমেন্ট তাদের গ্রুপের একজন রিপ্রেজেন্টেটিভ (Representative) বা লিডারের দিকে পয়েন্ট করে থাকে। দুজন স্টুডেন্ট তখনই ফ্রেন্ড সার্কেলে থাকবে, যখন তাদের লিডার একই মানুষ হবে। শুরুতে যেহেতু কারও সাথে কারও পরিচয় থাকে না, তাই সবাই নিজেই নিজের লিডার থাকে।

pseudocode

parent = [0, 1, 2, 3, 4]  // প্রত্যেকেই নিজের লিডার
rank   = [0, 0, 0, 0, 0]  // সব গ্রুপের সাইজ বা হাইট 0

◈ দেখুন কীভাবে পাথ কম্প্রেশন (path compression) হয়ে নোডগুলো জোড়া লাগে আর লিডার আপডেট হয়

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

পাথ কম্প্রেশন (Path Compression) দিয়ে লিডার খোঁজা

কারো গ্রুপের আসল লিডার কে, সেটা জানার জন্য একটা একটা করে প্যারেন্ট বা বসের কাছে যেতে থাকলে শেষমেশ লিডারের দেখা মিলবে। কিন্তু এতে তো সময় বেশি লাগবে, তাই না? এই জন্যই পাথ কম্প্রেশন (Path compression) নামে মারাত্মক একটা ট্রিক আছে: লিডারকে খুঁজতে খুঁজতে যানয়ার সময়, মাঝপথে যাদের সাথেই দেখা হবে, ফেরার সময় তাদের সবাইকে বলে দেওয়া হয় যে, "তোমরা এখন থেকে সরাসরি আসল লিডারের সাথেই কন্টাক্ট করবে।" ফলে, পরের বার যখন কেউ এদের খোঁজ নেবেনন, তখন এক লাফে O(1) সময়েই আসল লিডারকে পাওয়া যাবে!

pseudocode

function find(x):
  if parent[x] !== x:
    parent[x] = find(parent[x])  // পাথ কম্প্রেশন (Path compression)
  return parent[x]

র‍্যাংক দিয়ে গ্রুপ মেলানো (Union by Rank)

দুটো গ্রুপকে জোড়া লাগানোর বা এক করার উপায় হলো: এক গ্রুপের লিডারকে অন্য গ্রুপের লিডারের আন্ডারে ফেলে দেওয়া। ইউনিয়ন বাই র‍্যাংক (Union by rank)-এর বুদ্ধিটা হলো: সবসময় ছোট গ্রুপটাকে বড় গ্রুপের সাথে জুড়ে দেওয়া। এতে করে গ্রুপের ভেতরে হায়ারার্কি বা লম্বা চেইন তৈরি হয় না, সবাই লিডারের কাছাকাছি থাকে এবং পরে খুঁজতে কম সময় লাগে। আর যদি দুই গ্রুপের সাইজ সমান হয়, তবে যেকোনো একজনকে বস বানিয়ে তার র‍্যাংক বা উচ্চতা ১ বাড়িয়ে দেওয়া হয়।

pseudocode

function union(a, b):
  rootA = find(a)
  rootB = find(b)
  if rootA === rootB: return  // তারা তো আগে থেকেই একই গ্রুপে আছে!

  if rank[rootA] < rank[rootB]:
    parent[rootA] = rootB
  else if rank[rootA] > rank[rootB]:
    parent[rootB] = rootA
  else:
    parent[rootB] = rootA
    rank[rootA]++

কাজগুলো চোখের পলক বা O(1)-এ কীভাবে হয়?

পাথ কম্প্রেশন আর ইউনিয়ন বাই র‍্যাংক — এই দুই ট্রিক একসাথে ব্যবহার করলে, যেকোনো কাজ O(α(n)) অ্যামরটাইজড টাইমে হয়ে যায়। এখানে α হলো ইনভার্স অ্যাকারম্যান ফাংশন (inverse Ackermann function)। মহাবিশ্বে যত বড় সাইজের ইনপুটই দেওয়া হোক না কেন, প্র্যাকটিক্যালি α(n) -এর মান কখনোই ৪-এর বেশি হয় না। সহজ কথায়: এটা একদম কনস্ট্যান্ট টাইম বা চোখের পলকেই হয়ে যায়!

দ্রষ্টব্য: মিনিমাম স্প্যানিং ট্রি (MST) বের করার জন্য ক্রুসকালস (Kruskal's) অ্যালগরিদমের মূল মেরুদণ্ডই হলো এই ইউনিয়ন-ফাইন্ড। বারবার BFS বা DFS চালিয়ে 'এরা দুজন কানেক্টেড কি না' চেক করার চেয়ে ইউনিয়ন-ফাইন্ড এটা অনেক দ্রুত বা চোখের পলকে উত্তর দিতে পারে।