এর আগে আমরা মিনিমাম স্প্যানিং ট্রী এর প্রিমস এলগোরিদম টা ইমপ্লীমেন্ট করেছিলাম, এইবার আমরা ক্রুসকাল এলগোরিদম টা ইমপ্লিমেন্ট করবো এবং ক্রুসকাল দিয়ে একটা প্রবলেম সল্ভ করে দেখব!
এই কোডের রেফারেন্স হলো শাফায়াত ভাইয়ার ব্লগ। কেউ যদি সেইটা না পড়ে এইখানে আসেন, তাহলে আগে সেখান থেকে পড়ে আসুন প্লীজ। আর যদি সেইখান থেকে পড়ে সব কিছু অলরেডি বুঝেই যান, তাহলে এই লেখা আপনার জন্য না।
#include<bits//stdc++.h> using namespace std; #define MAXN 10000 struct hudai { int u,v,w; bool operator < ( const hudai& p ) const { return w < p.w; } }; int pr[MAXN]; vector<hudai>kop; int findset(int r) { if (pr[r]==r) return r; else return findset(pr[r]); } void makeset(int n) { for(int i=1;i<=n;i++)pr[i]=i; } void Kruskal(int n) { sort(kop.begin(),kop.end()); makeset(n); int sum=0; for(int i=0;i<(int)kop.size();i++) { int u=findset(kop[i].u); int v=findset(kop[i].v); if(u!=v) { pr[u]=v; sum+=kop[i].w; printf("%d-%d\n",kop[i].u,kop[i].v); } } printf("%d\n",sum); } int main(){ //freopen("in.txt","r",stdin); int n,m; cin>>n>>m;//n হলো node m হল এজ for(int i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w;//এজ আর ওয়েট নিলাম hudai aha; aha.u=u; aha.v=v; aha.w=w; kop.push_back(aha); } Kruskal(n); return 0; }
প্রথমে আমরা হুদাই টাইপের একটা ডাটাটাইপ বানালাম। এর পর এইখানে আমরা < অপারেটরকে ওভারলোড করে দিলাম। সি প্লাস প্লাসে ফাংশন ওভারলোডের মত অপারেটর ওভারলোডও করা যায়। ফাংশন ওভারলোডে যেমন একই নামের একাধিক ফাংশন থাকত, যাদের প্যারামিটার আলাদা…কারো ইন্টিজার, কারো ডাবল, এইখানেও আমরা অনেকটা একই কাজ করছি। ইন্টিজার টাইপের কিছু থাকলে সেটাকে < অপারেটর সহজেই তুলনা করে নিতে পারে।কিন্তু তা বাদে অন্য কোন টাইপের জিনিস আসলে?
এতখানি বুদ্ধি কম্পিউটারের থাকলে তো কোড করাই লাগত না ! আমাদের তাই বলে দিতে হবে কিসের বেসিসে আমরা তুলনা টা করবো!
আমরা তাই “hudai” টাইপের কোন অবজেক্ট যদি প্যারামিটার হিসেবে আসে তাহলে তাকে তার ওয়েটের ভ্যালু অনুসারে সাজাতে হবে- সেটাই বলে দিচ্ছি।
pr[MAXN] এরের ইনডেক্স হবে ভার্টেক্সগুলা , আর ভ্যালু গুলা রিপ্রেজেন্ট করবে সেইটা ভার্টেক্স কোন সেটের অন্তর্গত। দুইটা pr[প্রথম ভার্টেক্স] এবং pr[সেকেন্ড ভার্টেক্স] সমান হইলে আমরা বুঝব এরা একই সেটের অন্তর্গত, সো এদের মাঝে একটা সাইকেল আছে!
এইবারে কোপ হবে 😛 আমরা হুদাই টাইপের ডাটা টাইপ নিয়ে ভেক্টর বানালাম, যার নাম কোপ!
findset() ফাংশনের কাজ হলো একটা ইন্টিজার রিটার্ন করা, ইন্টিজার টা হবে সেই সেটের রিপ্রেজেন্টিটিভব।যদি দুইবার কল করা হয় আলাদা দুইটা ভার্টেক্স দিয়ে, এবং ভার্টেক্স দুইটা সেইম সেটের অন্তভুর্ক্ত হয়,তবে সেইম ইন্টিজার রিটার্ন করবে। ডিফারেন্ট সেটে ডিফারেন্ট ইন্টিজার রিটার্ন করবে।
এইবার ক্রুসকালে আসা যাক,প্রথমে আমরা ওয়েট অনুসারে এজ সর্ট করলাম।সেট বানালাম makeset() দিয়ে, এই ফাংশনটা প্রথমে প্রত্যেকটা ভার্টেক্স কে আলাদা আলাদা সেটে রাখবে, এবং সেই সেটের রিপ্রেজেন্টিটিভ সে নিজেই!
প্রত্যেকবার u and v তে দুইটা সেটের রিপ্রেজেন্টিটিভ গুলা এসাইন হবে, দুইটা সেটের রিপ্রেজেন্টিটিভ একই হলে, গ্রাফে সাইকেল আছে, ভিন্ন হইলে সাইকেল নাই। আর যদি সাইকেল না থাকে তাহলে একটা সেটের লেজে আরেকটা সেটের মাথা লাগায় দিবো, এখন দুইটা মিলে একটা সেট 😛
এরপর প্রতিবার যেই এজটা আসতেসে, সেই এজ আগের যোগফলের সাথে যোগ হচ্ছে আর সেই এজ প্রিন্ট হচ্ছে।
মেইন ফাংশনে হুদাই টাইপের একটা অবজেক্ট নিলাম… সেই অবজেক্টে এবার মানগুলো এসাইন করলাম।শেষে পুরা অবজেক্ট টাকে কোপের মাঝে ভরে দিয়ে (!) ক্রুসকালকে কল করলাম!! এবং আমাদের কাজ শেষ 😀