পাইথনে ম্যাক্সিমাম নেটওয়ার্ক র‍্যাঙ্ক বের করার প্রোগ্রাম

মান লিজিয়ে n সিটি আছে এবং কিছু রোড এগুলোকে কানেক্ট করে। roads[i] = [u, v] মানে সিটি u এবং v-এর মধ্যস্থ টু-ওয়ে রোড আছে। নেটওয়ার্ক র‍্যাঙ্ক হল দুটি সিটির সরাসরি কানেক্টেড রোডের মোট সংখ্যা। যদি এক রোড দুটো সিটির সাথে সরাসরি জড়িত থাকে, তবে সেটি একবারই কাউন্ট হবে। পুরো নেটওয়ার্কের ম্যাক্সিমাম নেটওয়ার্ক র‍্যাঙ্ক হল সব ভিন্ন সিটি জোড়ার নেটওয়ার্ক র‍্যাঙ্কের সর্বোচ্চ মান। রোডগুলো দিয়ে ম্যাক্সিমাম নেটওয়ার্ক র‍্যাঙ্ক বের করতে হবে।

যেমন, ইনপুট হলে (চিত্র দেখুন), তবে আউটপুট হবে 5 কারণ সিটি ১ ও ২ কানেক্ট করার পাঁচটি ভিন্ন উপায় আছে।

সমাধানের ধাপসমূহ

nodes := সেট, s := সেট, d := ডিফল্টডিক্ট(int)
roads-এ প্রতিটি (x,y) এর জন্য:
- d[x] += 1, d[y] += 1
- s.add((x,y))
ans := 0
l := range(n) থেকে বানানো লিস্ট, নোড নম্বর ডিসেন্ডিং সর্ট করুন।
threshold := min(d[l[0]], d[l[1]])
i = 0 থেকে len(l)-1 পর্যন্ত:
- j = i+1 থেকে len(l)-1 পর্যন্ত:
  - যদি d[l[j]] < threshold হয়, তবে ব্রেক করুন।
  - curr := d[l[i]] + d[l[j]]
  - যদি (l[i],l[j]) in s or (l[j],l[i]) in s হয়, তবে curr -= 1
  - ans = max(ans, curr)
ans রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

from collections import defaultdict
def solve(roads):
    nodes = set()
    s = set()
    d = defaultdict(int)
    for x, y in roads:
        nodes.update([x, y])
        d[x] += 1
        d[y] += 1
        s.add((x, y))
    ans = 0
    n = len(nodes)
    l = list(range(n))
    l.sort(key=lambda x: d[x], reverse=True)
    threshold = min(d[l[0]], d[l[1]])
    for i in range(len(l) - 1):
        for j in range(i + 1, len(l)):
            if d[l[j]] < threshold:
                break
            curr = d[l[i]] + d[l[j]]
            if (l[i], l[j]) in s or (l[j], l[i]) in s:
                curr -= 1
            ans = max(ans, curr)
    return ans

roads = [(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)]
print(solve(roads))

ইনপুট

[(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)]