পাইথনে গ্রাফে সর্বোচ্চ ক্লিকের ন্যূনতম আকার বের করার প্রোগ্রাম

মনে করুন একটি গ্রাফ দেওয়া আছে এবং আমাদের গ্রাফে সর্বোচ্চ ক্লিকের ন্যূনতম আকার বের করতে বলা হয়েছে। একটি গ্রাফের ক্লিক হলো গ্রাফের একটি সাবসেট যেখানে প্রতিটি ভের্টেক্স জোড়া আডজেসেন্ট, অর্থাৎ প্রতিটি জোড়ার মধ্যএ একটি এজ থাকে। গ্রাফে সর্বোচ্চ ক্লিক বের করা পলিনোমিয়াল টাইমে সম্ভব নয়, তাই একটি ছোট গ্রাফের নোড এবং এজ সংখ্যা দেওয়া থাকলে তার সর্বোচ্চ ক্লিক বের করতে হবে।

যেমন, ইনপুট নোডস = ৪, এজস = ৪ হলে, আউটপুট হবে ২।

উপরোক্ত গ্রাফে, ক্লিকের সর্বোচ্চ আকার ২।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

helper() ফাংশন ডিফাইন করুন। এটি x, y প্যারামিটার নেবে
- ga := x mod y
- gb := y - ga
- sa := x // y + 1
- sb := x // y
- return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2
i := 1, j := nodes + 1
যখন i + 1 < j, तब
- p := i + (j - i) // 2
- k := helper(nodes, p)
- যদি k < edges হয়, তবে
  - i := p
- অন্যথায়,
  - j := p
j রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

import math def helper(x, y):     ga = x % y     gb = y - ga     sa = x // y + 1     sb = x // y     return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2 def solve(nodes, edges):     i = 1     j = nodes + 1     while i + 1 < j:         p = i + (j - i) // 2         k = helper(nodes, p)         if k < edges:             i = p         else:             j = p     return j print(solve(4, 4))

ইনপুট

4,4