Reading Time: 2 minutes

ক্যাটাগরি : বিএফএস / ডিএফএস ।

প্রবলেম লিঙ্ক : https://uva.onlinejudge.org/external/3/336.html

প্রবলেম : এই প্রবলেমটিতে মূলত বলা হয়েছে, আমাদের কিছু ভার্টেক্স আর তাদের মধ্যে এজ দেয়া থাকবে । আর এগুলো দেয়ার পর আমাদের টেস্ট কেস হিসেবে দেয়া নোড গুলোর মধ্য থেকে কিছু নোড আর তাদের মধ্যের টাইম টু লিভ বা টিটিএল (TTL) দেয়া থাকবে । এই নোড থেকে শুরু করে আমাদের বের করতে হবে টিটিএল এর উপর বেস করে সর্বোচ্চ কয়টা নোড ভিজিট করা যাবে আর কতগুলো যাবে না । যতগুলো যাবে না আমাদের মূলত ঐ সংখ্যাটাই প্রিন্ট করতে হবে । টিটিএল বলতে বুঝিয়েছে আমরা স্টার্টিং নোড থেকে শুরু করে সর্বোচ্চ কতগুলো নোড একটানা ভিজিট করতে পারব বা একই পথে আমরা টানা কয়টা নোড পর্যন্ত যেতে পারব ।

এ প্রবলেমটির মূল অ্যাালগরিদম খুবই সোজা । শুধুমাত্র বিএফএস/লেভেল বাই লেভেল সার্চ করে আমাদের টিটিএল এর নম্বর যত তত লেভেল পর্যন্ত গেলে কতগুলো ভার্টেক্স ভিজিট করতে পারছি আর কতগুলো করতে পারছি না এটা বের করতে পারলেই যথেষ্ট ।

কিন্তু এর মূল সমস্যা হচ্ছে ইনপুটে । এখানে সব আর্বিটারি নোড দেয়া । এগুলোকে গ্রাফে গুছিয়ে স্টোর করাটাই এ প্রবলেম এর সবচাইতে বড় চ্যালেঞ্জ । আমি যেটা করেছিলাম সবগুলো ইনপুট নিয়ে ঐগুলো কে স্ট্রাকচারে রেখেছিলাম যেখানে মোটামুটি ৪টার মত উপাদান ছিল । ২টি হচ্ছে ২টি ভার্টেক্স যেগুলো দেয়া আর বাকি ২টা হচ্ছে আমরা এই ভার্টেক্স গুলোকে আমাদের সুবিধার জন্য কোন নাম দিচ্ছি সেটা । আমি নামটা এভাবে বার করেছিলাম, আমি প্রথমেই দেখেছিলাম আমার ইনপুট এর মধ্যে একদম ভিন্ন নাম্বার কয়টি আছে , সেই নাম্বারটিই নোড কয়টা আছে সেটা বুঝায় । এরপর ছোট থেকে বড়তে সর্ট করেছিলাম আর এদের ইনডেক্স নাম্বরটিকেই এদের নতুন নাম্বার দিয়েছিলাম যেটা নতুনভাবে নোড হিসেবে তাদেরকেই বুঝাবে ।

এভাবে আমি সব আর্বিটারি নোডগুলোকে একটা গুছানো অর্ডারে নিয়ে এসে গ্রাফে স্টোর করেছিলাম । তারপর খুবই সাধারণ ভাবে বিএফএস করে আমাদের আউটপুটটি বের করেছিলাম ।

Code :

আমরা প্রথমে নিজের চেষ্টা করব, নিতান্তই না পারলে নিচের কোডটি দেখে কিছু সাহায্য পেতে পারি ।