Python程式：查詢最大網路秩

假設有n個城市，一些道路連線這些城市。每個roads[i] = [u, v]表示城市u和v之間有一條雙向道路。現在考慮網路秩是直接連線到任一城市的道路總數。當一條道路直接連線到兩個城市時，只計算一次。整個網路的最大網路秩是所有不同城市對的最大網路秩。因此，如果我們有不同的道路，我們必須找到整個網路的最大網路秩。

因此，如果輸入如下所示：

則輸出將為5，因為有五種不同的方式連線城市1和2。

為了解決這個問題，我們將遵循以下步驟：

  • n := 節點數
  • s := 一個新的集合
  • d := 一個對映，如果某個鍵不存在，則返回0。
  • 對於roads中的每條邊(x,y)，執行：
    • d[x] := d[x] + 1
    • d[y] := d[y] + 1
    • 將(x,y)對插入d
    • ans := 0
  • l := 從0到n的一個新的列表
  • 根據節點號以降序對l排序
  • threshold := min(d[l[0]], d[l[1]])
  • 對於範圍0到l的大小-1中的i，執行：
    • 對於範圍i+1到l的大小-1中的j，執行：
      • 如果d[l[j]] < threshold，則
        • 退出迴圈
      • curr := d[l[i]] + d[l[j]]
      • 如果s中存在(l[i],l[j])或(l[j],l[i])，則
        • curr := curr - 1
      • ans := max(ans, curr)
  • 返回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

更新於：2021年10月5日

367 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.