পাইথনে অসুখী বন্ধুর সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে n(এমনকি) বিভিন্ন বন্ধুদের পছন্দের তালিকা রয়েছে। প্রতিটি ব্যক্তির জন্য i, পছন্দ[i] পছন্দের ক্রমে সাজানো বন্ধুদের একটি তালিকা রাখে। সুতরাং, তালিকায় আগের বন্ধুটি তালিকায় পরে থাকা বন্ধুর চেয়ে বেশি পছন্দ করে। প্রতিটি তালিকার বন্ধুদের 0 থেকে n-1 পর্যন্ত পূর্ণসংখ্যা দ্বারা সংখ্যা করা হয়েছে। বন্ধুরা সবাই বিভিন্ন জোড়ায় বিভক্ত। যেখানে জোড়া [i] =[xi, yi] প্রতিনিধিত্ব করে xi কে yi এর সাথে যুক্ত করা হয়েছে এবং/অথবা yi xi এর সাথে জোড়া হয়েছে৷ কিন্তু একজন বন্ধু x অসন্তুষ্ট হয় যদি x এর সাথে y যুক্ত হয় এবং সেখানে একজন বন্ধু u থাকে যাকে v এর সাথেও জোড়া হয় কিন্তু −

• x y এর চেয়ে u পছন্দ করে, এবং
• v এর চেয়ে x পছন্দ করে।

আমাদের অসুখী বন্ধুদের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট পছন্দের মত হয় =[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] জোড়া =[[0, 1] , [2, 3]], তাহলে আউটপুট হবে 2 কারণ প্রথম বন্ধু অসন্তুষ্ট কারণ ব্যক্তি 1 ব্যক্তি 0 এর সাথে যুক্ত কিন্তু ব্যক্তি 0 এর চেয়ে ব্যক্তি 3 কে পছন্দ করে এবং ব্যক্তি 3 ব্যক্তি 2 এর চেয়ে ব্যক্তি 1 কে পছন্দ করে। এবং বন্ধু 3 অসন্তুষ্ট। কারণ ব্যক্তি 3 ব্যক্তি 2 এর সাথে যুক্ত কিন্তু ব্যক্তি 2 এর চেয়ে ব্যক্তি 1 কে পছন্দ করে এবং ব্যক্তি 1 ব্যক্তি 0 এর চেয়ে ব্যক্তি 3 কে পছন্দ করে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• গ্রাফ :=গ্রাফ তৈরি করার জন্য একটি সংলগ্ন তালিকা, প্রাথমিকভাবে খালি
• প্রতি জোড়ার জন্য (s, e) জোড়ায়, করুন
  • অভিরুচি[গুলি]-এর প্রতিটি pref-এর জন্য, করুন
    • যদি pref শেষের মত হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
    • গ্রাফ[s, pref] :=1
  • পছন্দের প্রতিটি pref এর জন্য [e], করুন
    • যদি pref শুরু হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
    • গ্রাফ[e, pref] :=1
• অসুখী :=0
• প্রতি জোড়ার জন্য (s, e) জোড়ায়, করুন
  • গ্রাফ[s]-এর প্রতিটি pref-এর জন্য, করুন
    • যদি গ্রাফ[pref][s] খালি না হয়, তাহলে
      • অসুখী :=অসুখী + 1
      • লুপ থেকে বেরিয়ে আসুন
  • গ্রাফের প্রতিটি প্রিফের জন্য[শেষ], করুন
    • যদি গ্রাফ[pref][e] খালি না হয়, তাহলে
      • অসুখী :=অসুখী + 1
      • লুপ থেকে বেরিয়ে আসুন
• অসুখী ফিরে

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

সংগ্রহ থেকে আমদানি ডিফল্টডিক্ট ডিফ সমাধান(পছন্দ, জোড়া):শুরুর জন্য গ্রাফ =ডিফল্টডিক্ট(ডিক্ট) শুরু, জোড়ায় শেষ:পছন্দের জন্য [শুরু]:যদি pref ==শেষ:ব্রেক গ্রাফ[start][pref] =পছন্দের ক্ষেত্রে pref এর জন্য 1[end]:if pref ==start:break graph[end][pref] =1 unhappy =0 শুরুর জন্য, জোড়ায় শেষ:গ্রাফে pref এর জন্য[start]:if graph[pref].get (start, None):অসুখী +=গ্রাফে প্রিফের জন্য 1 বিরতি 3, 2, 0], [3, 1, 0], [1, 2, 0]]জোড়া =[[0, 1], [2, 3]]প্রিন্ট(সল্ভ(পছন্দ, জোড়া))

ইনপুট

আউটপুট

2