মডিউল ১৪_৫ঃ Building Roads

বাইটল্যান্ডে রয়েছে n শহর এবং তাদের মধ্যে রয়েছে m রাস্তা । আপ্লনার কাজ হল নতুন রাস্তা তৈরি করা যাতে যেকোনো দুটি শহরের মধ্যে একটি রুট থাকে। আপনার কাজ হল minimum কতগুলি রাস্তা প্রয়োজন তা খুঁজে বের করা এবং কোন রাস্তাগুলি তৈরি করা উচিত তা বের করা।

ইনপুট

4 2

1 2

3 4

উপরের ইনপুটের গ্রাফটি

এখন এই গ্রাফের ইনপুট edge গুলো থেকে node এর leader বের করে করে union করলে এইরকমভাবে গ্রুপ হয়ে যাবে।

এইভাবে আমরা গ্রুপ গুলোর লিডারদেরকে connection করে দিলে আমরা এই প্রব্লেমটি সমাধান করে ফেলতে পারবো।