पायथन में अधिकतम नेटवर्क रैंक खोजने का कार्यक्रम

मान लीजिए कि 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
- जोड़ी (x,y) को d में डालें
- उत्तर:=0
l :=0 से n तक की एक नई सूची
नोड संख्याओं के आधार पर l को अवरोही क्रम में क्रमबद्ध करें
दहलीज:=न्यूनतम d[l[0]] और d[l[1]]
i के लिए 0 से लेकर l-1 के आकार तक के लिए
- j के लिए i+1 से l-1 के आकार के लिए, do
  - अगर d[l[j]] <दहलीज, तो
    - लूप से बाहर आएं
  - कर्र:=डी[एल[i]] + डी[एल[जे]]
  - अगर (l[i],l[j]) s में मौजूद है या (l[j],l[i]) s में मौजूद है, तो
    - करा :=curr - 1
  - उत्तर :=अधिकतम उत्तर और वर्तमान
वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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