Light OJ - 1168 Tutorial

Problem Description here

Prerequisite of this problem DFS, Strongly Connected Component(SCC)

Problem:

সহজ ভাষায় বলতে গেলে এই প্রব্লেমে মূলত বলা হয়েছে, আমাকে অনেকগুলো এজ দেয়া থাকবে। ০ নোড থেকে যাত্রা শুরু করে সবগুলো এজ এক্সেক্টলি ১ বার ভিজিট করা সম্ভব কি না বের করতে হবে। 

Solution:

১) SCC সম্পর্কে ধারণা থাকলে এবং একটু চিন্তা করলেই দেখবে যে, SCC এর যেকোন নোড থেকে যাত্রা শুরু করে সবগুলো এজ এক্সেক্টলি ১বার ভিজিট করা সম্ভব। 

২) তাহলে, এই প্রব্লেমে আমার প্রথম কাজ হচ্ছে, গ্রাফটিকে অনেকগুলো SCC তে ভাগ করা। এখন, প্রতিটি কম্পোনেন্টকে একটি নোড কল্পনা করলে দেখবে যে একটি DAG(Directed Acyclic Graph) তৈরী হয়। 

৩) এখন, নতুন এই DAG এর জন্য আমাকে দেখতে হবে ০ নোড থেকে যাত্রা শুরু করে সবগুলো এজ এক্সেক্টলি ১বার ভিজিট করা যায় কি না? অর্থাৎ, আমাকে দেখতে হবে যে DAG এর প্রতিটি নোডের Child সর্বোচ্চ একটির মধ্যে সীমাবদ্ধ কি না এবং ০ থেকে যাত্রা শুরু করে সকল নোড ভিজিট করা যায় কি না। 

আশা করি এখন প্রব্লেমটি নিজে নিজেই সলভ করা সম্ভব।

তাও ব্যার্থ হলে কোড দেখতে পারোঃ 

Happy Coding 😊