Pythonで都市ネットワークの最大ネットワークランクを求めるプログラム

n個の都市があり、いくつかの道路によって相互に接続されているとします。roads[i] = [u, v] は、都市uと都市vの間に双方向の道路が1本存在することを表します。

ここで「ネットワークランク」とは、ある2つの異なる都市のペアについて、そのどちらかの都市に直接接続されている道路の総数を指します。ただし、2つの都市の両方に直接つながっている道路は、重複を避けるために1本としてのみカウントします。そして「最大ネットワークランク」とは、取り得るすべての都市ペアの中で最も大きなネットワークランクの値のことです。与えられた道路情報をもとに、ネットワーク全体の最大ネットワークランクを求めましょう。

問題の例

例えば、次のような入力が与えられたとします。

この場合の出力は 5 になります。都市1と都市2のペアに注目すると、都市1には3本の道路（都市0・2・3へ）、都市2にも3本の道路（都市1・3・4へ）が直接接続されています。合計は6本ですが、両都市を直接結ぶ道路(1, 2)が二重に数えられるため、6 − 1 = 5 がこのペアのネットワークランクとなり、これが全体の最大値になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• n := ノード（都市）の総数
• s := 辺（道路）を記録するための新しい集合
• d := 各ノードの次数（直接つながる道路の本数）を格納するマップ。キーが存在しない場合は0を返す
• roads 内の各辺 (x, y) について以下を実行する:
  • d[x] := d[x] + 1
  • d[y] := d[y] + 1
  • ペア (x, y) を s に挿入する
• ans := 0（答えを保持する変数）
• l := 0 から n−1 までのノード番号のリストを作成する
• l を各ノードの次数の降順でソートする
• threshold := d[l[0]] と d[l[1]] の小さい方（上位2ノードの次数の最小値）
• i を 0 から len(l)−2 まで繰り返す:
  • j を i+1 から len(l)−1 まで繰り返す:
    • d[l[j]] < threshold の場合はループを抜ける（枝刈り）
    • curr := d[l[i]] + d[l[j]]
    • (l[i], l[j]) または (l[j], l[i]) が s に存在する場合、curr := curr − 1（共有道路の重複を除去）
    • ans := ans と curr の最大値
• ans を返す

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

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

アルゴリズムのポイント

• 次数の集計： まず各都市に直接つながる道路の本数（次数）を defaultdict で効率よく集計します。
• 降順ソートによる探索の絞り込み： 最大ランクの候補は次数の大きい都市同士のペアに現れるため、ノードを次数の降順に並べて前方から調べます。
• 枝刈り： 上位2ノードの次数の最小値を threshold とし、それを下回るノードが出た時点で内側のループを打ち切ることで、無駄な計算を省きます。
• 重複の除去： 2つの都市が直接つながっている場合、その道路は両都市の次数に含まれるため、合計から1を引いて補正します。

計算量は、ソートに O(n log n)、ペアの全探索に最悪で O(n²) かかりますが、枝刈りによって実際の計算量は大幅に抑えられます。