Bappy's Blog

Problem Description  here Topic Of This Problem: Dijkstra ১) প্রথমত, অলরেডি এক্সিস্টিং রোড এবং নতুন রোড দুইটি আলাদা ভেক্টরে রাখতে হবে। এবং তাদের কস্টও আলাদা আলাদা ভেক্টরে রাখতে হবে। ২) সাধারণত, ডায়াক্সট্রা তে আমরা প্রায়োরিটি কিউ তে দুইটি ইনফরমেশন রাখি। একটি নোড এবং স্টার্টিং নোড থেকে এই নোডে আসার কস্ট। এখানে আরো একটি ইনফরমেশন রাখা লাগবে। আর তা হলো, এই নোডে আসতে নতুন কয়টা রোড আমি ব্যাবহার করেছি। ৩) স্টার্টিং নোড থেকে প্রতিটি নোডের দূরুত্ব রাখার জন্য আগে আমরা 1D array ব্যাবহার করতাম। আর এখন ব্যাবহার করবো 2D Array . অ্যারের arr[x][y] - নির্দেশ করে স্টার্টিং নোড থেকে x নোডে , y সংখ্যক নতুন রোড ব্যাবহার করে আসার কস্ট। ৪) এরপর আমরা প্রায়োরিটি কিউ এর প্রতিটি এলিমেন্ট ব্যাবহার করে, প্রথমে ওই এলিমেন্ট থেকে এক্সিস্টিং রোড দ্বারা যতোদিকে যাওয়া যায়, গিয়ে কস্ট আপডেট করে দিবো। এরপর, ওই এলিমেন্ট থেকে নতুন রোড দ্বারা যতোদিকে যাওয়া যায় গিয়ে কস্ট আপডেট করবো। সবশেষে ডেস্টিনেশন নোডে ০ থেকে d সংখ্যক নতুন রোড ব্যাবহার করে যেসব কস্টে পৌঁছানো যায় তাদের মধ্যে সর্বনিম্ন কস্ট ই এন্সার। ডায়াক্সট্...

Topic Of This Problem: DFS or BFS Problem Description:  here ১) প্রব্লেম ডেসক্রিপশন অনুযায়ী প্রতিটি নোডের সর্বোচ্চ দুইটা অবস্থা থাকতে পারে।  -> এই নোডে তারা উভয়েই এককভাবে দৌড়ে প্রবেশ করবে।  -> হানজো অন্যজনকে ক্যারি করে প্রবেশ করবে।  ২) টেস্ট কেসে সাইকেল থাকলে একই নোডে একবার তারা প্রথম স্টেট অনুযায়ী প্রবেশ করে তো অন্যবার ২য় স্টেট অনুযায়ী প্রবেশ করতেও পারে।  ৩) এখন আমরা DFS চালিয়ে বর্তমান নোডে আমি যেই অবস্থায় প্রবেশ করেছি, তার এডজাসেন্ট নোডগুলোতে তার ঠিক উলটো অবস্থায় প্রবেশ করার চেষ্টা করবো যদি না এই উলটো অবস্থায় অলরেডি ওই এডজাসেন্ট নোডে প্রবেশ করে না থাকি।  ৪) সবশেষে হিসেব করবো যে স্টেট-২ এর জন্য কয়টি নোড ভিসিট করা হয়েছে। ডিএফএস সম্পর্কে জানতে  ক্লিক করুন  বিএফএস সম্পর্কে জানতে  ক্লিক করুন

Topics of this problem: Strongly Connected Component(SCC) ১) প্রথমেই গ্রাফটির স্ট্রংলি কানেক্টেড কম্পোনেন্ট বের করতে হবে। এবং প্রতিটি কম্পোনেন্ট এর সাইজ এবং ওই কম্পোনেন্ট এ থাকা নোডগুলোর মধ্যে সর্বনিম্ন নোড টি মনে রাখতে হবে।  ২) এরপর, যেই অর্ডার এ গ্রাফটির SCC বের করা হয়েছে তার ঠিক উলটো অর্ডার এ আবার DFS চালাতে হবে। ( মানে তুমি যদি SCC তে স্ট্যাক ব্যাবহার কর, এবার QUEUE ব্যাবহার করবে -_- ) DFS চালিয়ে দেখতে হবে এই কম্পোনেন্ট কোন কোন কম্পোনেন্ট কে স্পর্শ করে। অর্থাৎ, এই কম্পোনেন্ট থেকে কোন কোন কম্পোনেন্ট এ যাওয়া যায়। সেইসব কম্পোনেন্ট এর সাইজকে এই কম্পোনেন্ট এর সাইজের সাথে যোগ করে দিবো। ৩) এবার দেখবে, প্রতিটি কম্পোনেন্ট এর সাইজ কত? যে কম্পোনেন্ট এর সাইজ সর্বোচ্চ সে কম্পোনেন্ট এর সর্বনিম্ন নোড টি আউটপুট হবে। যদি একাধিক কম্পোনেন্ট এর সাইজ সমান পাওয়া যায়, তবে তাদের নোডগুলোর মধ্যে সর্বনিম্ন নোড টি হবে আউটপুট। SCC সম্পর্কে জানতে  ক্লিক করুন