Chương trình tìm xếp hạng mạng tối đa bằng Python

Giả sử có n thành phố và có một số con đường nối các thành phố này. Mỗi con đường [i] =[u, v] chỉ ra rằng có đường hai chiều giữa các thành phố u và v. Bây giờ, hãy coi xếp hạng mạng là tổng số đường được kết nối trực tiếp đến một trong hai thành phố. Khi một con đường được kết nối trực tiếp với cả hai thành phố, nó chỉ được tính một lần. Và thứ hạng mạng tối đa của mạng là thứ hạng mạng tối đa của tất cả các cặp thành phố khác nhau. Vì vậy, nếu chúng ta có các con đường khác nhau, chúng ta phải tìm thứ hạng mạng tối đa của toàn bộ mạng.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 5 vì có năm cách khác nhau để kết nối các thành phố 1 và 2

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=số nút
• s:=một tập hợp mới
• d:=một bản đồ, nếu một số khóa không có thì trả về 0 cho nó
• đối với mỗi cạnh (x, y) trên đường, thực hiện
  • d [x]:=d [x] + 1
  • d [y]:=d [y] + 1
  • chèn cặp (x, y) vào d
  • ans:=0
• l:=một danh sách mới từ phạm vi 0 đến n
• sắp xếp l dựa trên số nút theo thứ tự giảm dần
• ngưỡng:=tối thiểu là d [l [0]] và d [l [1]]
• đối với tôi trong phạm vi từ 0 đến kích thước l - 1, thực hiện
  • đối với j trong phạm vi i + 1 đến kích thước l - 1, thực hiện
    • nếu d [l [j]]
    • ra khỏi vòng lặp
  • curr:=d [l [i]] + d [l [j]]
  • nếu (l [i], l [j]) có trong s hoặc (l [j], l [i]) có trong s, thì
    • curr:=curr - 1
  • ans:=tối đa ans và curr

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

5