[ UVa ] 10600 - ACM Contest and Blackout

• এই সমস্যা তে আমাদের কে 2nd best MST বের করেত হবে । 
• এই সমস্যা সমাধান করার জন্য আমাদের কে প্রথমে MST বের করতে হবে । এবং এই MST তে যে এজ গুলি নেয়া হয়েছে সেগুলো ইন্ডিকেট করে রাখতে হবে । 
• এখন এই MST এর এজগুলি থেকে প্রতিবার একটা করে এজ বাদ দিয়ে নতুন MST গঠন করার চেষ্টা করবো । এবং সেটার মোট খরচ কত হয় সেটা হিসাবে করে রাখব । 
• আমরা যখন আমাদের MST থেকে কোন এজ বাদ দিয়ে নতুন একটা ST বানাতে চেষ্টা করবো তখন শেষে আমাদেরকে চেক করতে হবে যে এই এজ টি বাদ দিয়ে আসলেই MST বানানো সম্ভব কি না ? 
• এটা নিশ্চিত করার জন্য যখন আমাদের MST বানানো শেষ হবে তখন দেখতে হবে যে আমাদের সবগুলি নোড একই সেটের মধ্যে আছে কি না ?
• যদি সবগুলি একই সেটের মধ্যে না থাকে তবে বুঝতে হবে । আমরা যে এজ কে বাদ দিয়ে MST বানানোর চেষ্টা করেছি । সেই এজ কে বাদ দিয়ে আসলে MST বানানো সম্ভব না ।
• এই ভাবে যতগুলো MST গঠন করা যাবে তাদের মধ্যে যেটার খরচ সবচেয়ে কম সেটাই আমাদের 2nd best Minimum Spanning Tree .  

কোড :

Happy Coding :)