পাইথনে সর্বাধিক নেটওয়ার্ক র‌্যাঙ্ক খোঁজার প্রোগ্রাম

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

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 5 কারণ শহর 1 এবং 2

কে সংযুক্ত করার জন্য পাঁচটি ভিন্ন উপায় রয়েছে

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

n :=নোডের সংখ্যা
s :=একটি নতুন সেট
d :=একটি মানচিত্র, কিছু কী উপস্থিত না থাকলে তার জন্য 0 ফেরত দিন
রাস্তার প্রতিটি প্রান্তের (x,y) জন্য, করুন
- d[x] :=d[x] + 1
- d[y] :=d[y] + 1
- d-এ জোড়া (x,y) ঢোকান
- উত্তর :=0
l :=0 থেকে n পর্যন্ত একটি নতুন তালিকা
নোড সংখ্যার উপর ভিত্তি করে l সাজান ক্রমানুসারে
থ্রেশহোল্ড :=সর্বনিম্ন d[l[0]] এবং d[l[1]]
আমি 0 থেকে l - 1 এর পরিসরের জন্য, কর
- j এর জন্য i+1 থেকে l - 1 এর আকারের মধ্যে, do
  - যদি d[l[j]] <থ্রেশহোল্ড হয়, তাহলে
    - লুপ থেকে বেরিয়ে আসুন
  - curr :=d[l[i]] + d[l[j]]
  - যদি (l[i],l[j]) s-এ থাকে বা (l[j],l[i]) s-এ থাকে, তাহলে
    - curr :=curr - 1
  - উত্তর :=সর্বাধিক উত্তর এবং curr
উত্তর ফেরত দিন

উদাহরণ

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

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)]