শাফায়েতের ব্লগ

সিপিপি তো সর্ট আর স্টেবল সর্ট নামের দুটি পৃথক ফাংশন আছে। এই পোস্টের উদ্দেশ্য এদুটির পার্থক্য দেখানো,কিভাবে ব্যবহার করতে হয় শিখানো না। আজকে codeforces কনটেস্টে জিনিসটা মাথায় না থাকার কারণে একদম সহজ প্রবলেমে বিশাল ধরা খেয়েছি। প্রবলেমটির লিংক: http://www.codeforces.com/problemset/problem/63/A এখানে বলা হয়েছে নিচের মত নামের লিস্ট দেয়া হবে: 6 Jack captain Alice woman Charlie man Teddy rat Bob child Julia woman এটাকে সর্ট করতে হবে এমন ভাবে যেন rat রা সবার সামনে আসে,তারপর woman আর child (এদের precedence সমান),তারপর man ও সবশেষে ক্যাপ্টেন। দুজনের precedence সমান হলে যাকে আগে ইনপ...

আগের পর্ব সবগুলো পর্ব এই পর্বে গ্রাফ স্টোর করার ২য় পদ্ধতি অ্যাডজেসেন্সি লিস্ট নিয়ে লিখব। এ পদ্ধতিতে গ্রাফ স্টোর করে কম মেমরি ব্যবহার করে আরো efficient কোড লেখা যায়। এ ক্ষেত্রে আমরা ডায়নামিক্যালি মেমরি অ্যালোকেট করব,ভয়ের কিছু নেই সি++ এর standard template library(STL) ব্যবহার করে খুব সহজে কাজটা করা যায়। আগের লেখার শেষের দিকে STL এর উপর কয়েকটি টিউটোরিয়ালের লিংক দিয়েছি, আশা করছি ভেক্টর কিভাবে কাজ করে এখন তুমি জানো। অ্যাডজেসেন্সি লিস্ট শুনতে যতটা ভয়ংকর শুনায়,ব্যাপারটি আসলে তেমনই সহজ। আমরা আবার আগের পোস্টের ছবিটিতে ফিরে যাই: এবার বাজার করার লিস্টের মত একটি লিস্ট বানাই: ...

আগের পোস্টে আমরা দেখেছি গ্রাফ থিওরি কি কাজে লাগে,আর এলিমেন্টারি কিছু টার্ম শিখেছি। এখন আমরা আরেকটু ভিতরে প্রবেশ করবো। প্রথমেই আমাদের জানা দরকার একটা গ্রাফ কিভাবে ইনপুট নিয়ে স্টোর করে রাখা যায়। অনেকগুলো পদ্ধতির মধ্যে দুটি  খুব কমন: ১. অ্যাডজেসেন্সি ম্যাট্রিক্স(adjacency matrix) ২. অ্যাডজেসেন্সি লিস্ট(adjacency list) অ্যাডজেসেন্ট(adjacent) শব্দটার অর্থ "কোন কিছুর পাশে"। যেমন তোমার পাশের বাড়ির প্রতিবেশিরা  তোমার অ্যাডজেসেন্ট। গ্রাফের ভাষায় এক নোডের সাথে আরেকটা নোডে যাওয়া গেলে ২য় নোডটি প্রথমটির অ্যাডজেসেন্ট। এই পোস্টে আমরা ম্যাট্রিক্সের সাহায্যে কোন নোড কার অ্যাডজেসেন্ট অ...

(গ্রাফ অ্যালগরিদম বইটি অনলাইনে পাওয়া যাচ্ছে রকমারি.কম এ। এছাড়াও নীলক্ষেতে হক, মানিক এবং রানা লাইব্রেরিতে বইটি পাওয়া যাচ্ছে) তুমি কি জানো পৃথিবীর প্রায় সব রকমের প্রবলেমকে কিছু রাস্তা আর শহরের প্রবলেম বানিয়ে সলভ করে ফেলা যায়? গ্রাফ থিওরির যখন জন্ম হয় তখন তোমার আমার কারোই জন্ম হয়নি, এমনকি পৃথিবীতে কোন কম্পিউটারও ছিলোনা! সেই সতেরো দশকের শেষের দিকে লিওনার্দ অয়লার গ্রাফ থিওরি আবিষ্কার করেন কনিসবার্গের সাতটি ব্রিজের সমস্যার সমাধান করতে। তখনই সবার কাছে পরিস্কার হয়ে যায় যে যেকোন প্রবলেমকে শহর-রাস্তার প্রবলেম দিয়ে মডেলিং করে চেনা একটা প্রবলেম বানিয়ে ফেলতে গ্রাফ থিওরির জুড়ি নেই। আর যখনই তুমি একটা...