โปรแกรมค้นหาอันดับเครือข่ายสูงสุดใน Python

สมมติว่ามี 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 ให้ทำ
    • ถ้า d[l[j]] <ธรณีประตู แล้ว
      • ออกมาจากลูป
    • curr :=d[l[i]] + d[l[j]]
    • ถ้า (l[i],l[j]) มีอยู่ใน s หรือ (l[j],l[i]) มีอยู่ใน s ดังนั้น
      • curr :=curr - 1
    • ans :=สูงสุดของ ans และ 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)]

ผลลัพธ์

5