জাভাস্ক্রিপ্টে গ্রাফের কানেক্টেড কম্পোনেন্ট খুঁজে বের করা

নিচের ইনপুট এবং আউটপুট অ্যারে বিবেচনা করুন:

const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];
const output = [
  [0, 1, 3],
  [4, 5, 6, 8]
];

প্রতিটি সংখ্যাকে একটি গ্রাফের নোড এবং প্রতিটি পেয়ারিং x:y কে নোড x এবং y-এর মধ্যে একটি এজ হিসেবে বিবেচনা করলে, আমাদের এজগুলোর মাধ্যমে যেটি ট্রাভার্স করা যায় এমন সংখ্যাগুলোর সেট খুঁজে বের করতে হবে।

অর্থাৎ, গ্রাফ থিওরির ভাষায়, এমন একটি গ্রাফে পৃথক কানেক্টেড কম্পোনেন্ট খুঁজে বের করতে হবে। উদাহরণস্বরূপ, উপরের অ্যারেতে ৪ থেকে ০-এ যাওয়া যায় না তাই সেগুলো আলাদা গ্রুপে, কিন্তু ১ থেকে ০-এ যাওয়া যায় (৩ দিয়ে) তাই সেগুলো একই গ্রুপে।

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা দেওয়া ইনপুট থেকে ডিজায়ারড আউটপুট তৈরি করবে।

উদাহরণ

const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];
const groupRange = (arr = []) => {
  const res = [[]];
  let count = 0;
  const a = [0];
  let array = arr.map(el=> el.split(':').sort((a, b) => a - b)).sort((a, b) => a[0] - b[0]);
  array.forEach(el => {
    if (el[0] > a[a.length - 1]) {
      res.push(el);
      a.push(el[1]);
      count++;
    } else {
      res[count] = res[count].concat(el);
      a[a.length - 1] = el[1];
    };
  });
  return res.map(el => [...new Set(el)].sort((a, b) => a - b));
}
console.log(groupRange(input));

আউটপুট

কনসোলে আউটপুট হবে:

[ [ '0', '1', '3' ], [ '4', '5', '6', '8' ] ]