পরিচয়
ডিসজয়েন্ট সেট (Disjoint Set) বা ইউনিয়ন-ফাইন্ড (Union-Find) একটি ডেটা স্ট্রাকচার যা একটি সেটকে অপরিবর্তনীয় সাবসেটে ভাগ করে রাখে। এটি দুটি প্রধান অপারেশন সাপোর্ট করে: Find এবং Union।
অপারেশনসমূহ:
- MakeSet(x): প্রতিটি এলিমেন্টকে আলাদা একটি সেটে রাখে (parent[x] = x)।
- Find(x): x-র রিপ্রেজেন্টেটিভ (রুট) ফেরত দেয়। পাথ কমপ্রেশন (path compression) ব্যবহার করে অপ্টিমাইজ করা যায়।
- Union(x, y): দুটি সেটকে মার্জ করে। ইউনিয়ন বাই র্যাঙ্ক (union by rank) ব্যবহার করে ট्री আঁচড় রাখা যায়।
উদাহরণ কোড (অপ্টিমাইজড ভার্সন)
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class DisjointSet {
unordered_map<int, int> parent;
unordered_map<int, int> rank;
public:
void makeSet(vector<int> const &universe) {
for (int i : universe) {
parent[i] = i;
rank[i] = 0;
}
}
int Find(int x) {
if (parent[x] != x)
parent[x] = Find(parent[x]); // Path Compression
return parent[x];
}
void Union(int x, int y) {
int xRoot = Find(x);
int yRoot = Find(y);
if (xRoot == yRoot) return;
// Union by Rank
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[xRoot] > rank[yRoot])
parent[yRoot] = xRoot;
else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
void printSets(vector<int> const &universe) {
for (int i : universe)
cout << Find(i) << " ";
cout << "\n";
}
};
int main() {
vector<int> universe = {6, 7, 1, 2, 3};
DisjointSet ds;
ds.makeSet(universe);
ds.Union(7, 6);
cout << "ইউনিয়ন(7,6) এর পর: ";
ds.printSets(universe);
cout << "Find(7) == Find(6): " << (ds.Find(7) == ds.Find(6) ? "Yes" : "No") << "\n";
cout << "Find(3) == Find(4): " << (ds.Find(3) == ds.Find(4) ? "Yes" : "No") << "\n";
return 0;
}আউটপুট
ইউনিয়ন(7,6) এর পর: 6 6 1 2 3 Find(7) == Find(6): Yes Find(3) == Find(4): No
ব্যবহার ক্ষেত্র
- ক্রুস্কালের এমএসটি (MST) অ্যালগরিদম
- সাইকেল ডিটেকশন অ্যান্ডিরেক্টেড গ্রাফে
- নেটওয়ার্ক কানেক্টিভিটি
- ইমেজ প্রসেসিং (কানেক্টেড কম্পোনেন্ট লেবেলিং)
ব্যাখ্যা
পাথ কমপ্রেশন এবং ইউনিয়ন বাই র্যাঙ্ক দুটো একসাথে ব্যবহার করলে অ্যামর্টাইজড টাইম কমপ্লেক্সিটি প্রায় O(α(n)) হয়, যা প্রায় কনস্ট্যান্ট। এই ইমপ্লিমেন্টেশনে `unordered_map` ব্যবহার করা হয়েছে যাতে যেকোনো ইন্টিজার ভ্যালু হ্যান্ডেল করা যায়।
