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

मान लीजिए n शहर हैं और कुछ सड़कें इन शहरों को जोड़ती हैं। प्रत्येक roads[i] = [u, v] दर्शाता है कि शहर u और v के बीच एक दो-तरफा सड़क है। अब नेटवर्क रैंक पर विचार करें जो किसी भी शहर से सीधे जुड़ी सड़कों की कुल संख्या है। जब एक सड़क दोनों शहरों से सीधे जुड़ी होती है, तो इसे केवल एक बार गिना जाता है। और पूरे नेटवर्क की अधिकतम नेटवर्क रैंक सभी अलग-अलग शहर जोड़ियों की अधिकतम नेटवर्क रैंक है। तो, यदि हमारे पास अलग-अलग सड़कें हैं, तो हमें पूरे नेटवर्क की अधिकतम नेटवर्क रैंक ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है: तो आउटपुट 5 होगा क्योंकि शहर 1 और 2 को जोड़ने के पांच अलग-अलग तरीके हैं।

समाधान के चरण

1. n := नोड्स की संख्या
2. s := set()
3. d := defaultdict(int) (यदि कोई कुंजी मौजूद नहीं है तो 0 वापस करें)
4. roads में प्रत्येक एज (x,y) के लिए:
   • d[x] += 1
   • d[y] += 1
   • s.add((x,y))
5. ans := 0
6. l := list(range(n))
7. l को नोड नंबर के आधार पर डिसेंडिंग ऑर्डर में सॉर्ट करें
8. threshold := min(d[l[0]], d[l[1]])
9. 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]) s में मौजूद है या (l[j],l[i]) s में मौजूद है:
       • curr := curr - 1
     • ans := max(ans, curr)
10. 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)]

आउटपुट

5