在 Python 中查找最大网络秩的程序

在 Python 中查找最大网络秩的程序

假设有 n 个城市,这些城市之间有一些道路相连。每个 roads[i] = [u,v] 都表示城市 u 和城市 v 之间有一条双向道路。现在考虑网络秩是与任一城市直接连接的道路总数。当一条道路直接连接两个城市时,它仅计数一次。网络的最大秩是所有不同的城市对的最大秩。因此,如果我们有不同的道路,我们需要找到整个网络的最大网络秩。

因此,如果输入如下所示:

在 Python 中查找最大网络秩的程序

则输出值将为 5,因为有 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 进行排序
  • threshold := d[l[0]] 和 d[l[1]] 中的最小值
  • 对于 i 在 0 到 l 的大小之间进行循环,执行以下操作:
    • 对于 j 在 i+1 到 l 的大小之间进行循环,执行以下操作:
      • 如果 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 := 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程