Pythonで最大のネットワークランクを見つけるプログラム

n個の都市があり、これらの都市を結ぶ道路がいくつかあるとします。各roads[i]=[u、v]は、都市uとvの間に双方向の道路があることを示します。ネットワークランクは、いずれかの都市に直接接続されている道路の総数であると考えてください。道路が両方の都市に直接接続されている場合、1回だけカウントされます。また、ネットワークの最大ネットワークランクは、異なる都市のすべてのペアの最大ネットワークランクです。したがって、道路が異なる場合は、ネットワーク全体の最大ネットワークランクを見つける必要があります。

したがって、入力が次のような場合

都市1と2を接続する方法は5つあるため、出力は5になります

これを解決するには、次の手順に従います-

• 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の場合、do
  • 範囲i+1からl-1のサイズのjの場合、do
    • 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