用 Python 编写的查找最大网络等级的程序

pythonserver side programmingprogramming更新于 2025/11/30 1:16:17

假设有 n 个城市，并且有一些道路连接这些城市。每个 roads[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
- ans := 0
l := 从 0 到 n 的新列表
根据节点号按降序对 l 进行排序
阈值 := d[l[0]] 和 d[l[1]] 中的最小值
对于范围为 0 到 l - 1 大小的 i，执行
- 对于范围为 i+1 到 l - 1 大小的 j，执行
  - 如果 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 的最大值
返回 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))