Day 145-Q4 — Nagamochi-Ibarakiのスパース化（K-辺連結性証明書の構築）

問題

$N$ 頂点 $M$ 辺の単純無向グラフ（辺重みなし、多重辺・自己ループなし）と整数 $K$ が与えられる。Nagamochi-Ibaraki法による $K$-辺連結性証明書（sparse certificate）を次の手順で構築せよ。

1. 証明書に含める辺集合 $F = \emptyset$ から開始する。
2. $i = 1, \dots, K$ について以下を繰り返す:
   • 現在の証明書 $F$ を用いて Maximum Adjacency Scan（頂点1から開始）を行う。未訪問頂点のうち、証明書 $F$ における既訪問頂点への接続本数が最大の頂点を次々に選ぶ（同点は頂点番号が小さい方を優先）。
   • 訪問順で2番目以降の各頂点 $v$ について、$v$より前に訪問された頂点の中から元のグラフ上で$v$と隣接し、まだ$F$に無い辺のうち、直前に訪問された頂点との辺を最優先し、無ければ最後に訪問された隣接頂点との辺を1本選び$F$に追加する。
3. 最終的な $F$ の辺数を出力せよ。

この証明書$F$は、元のグラフが持つサイズ$K$以下の全てのカットを正確に保持することが理論的に保証されており、$|F|\le K(N-1)$本に収まる。

入力形式

N M K
u_1 v_1
:
u_M v_M

制約

入出力例

4 5 2
1 2
2 3
3 4
4 1
1 3

5

$K=2$回のMAスキャンで、元の5辺のグラフの辺連結性を保つのに5辺全てが証明書に含まれる例。

概念図：Maximum Adjacency Scan

ヒント（段階的開示）

visited = [False] * (N + 1)
weight = [0] * (N + 1)  # F_adjにおける既訪問頂点への接続本数
order = [start]
visited[start] = True
for w in F_adj[start]:
    weight[w] += 1
for _ in range(N - 1):
    u = max((v for v in range(1, N+1) if not visited[v]),
            key=lambda v: (weight[v], -v))
    visited[u] = True
    order.append(u)
    # order[-2](直前訪問)を最優先して元グラフの隣接辺を1本選びFに追加
    for w in F_adj[u]:
        weight[w] += 1

模範解答 (Python)

📋 コピーimport sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1

    orig_adj = [set() for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        orig_adj[u].add(v)
        orig_adj[v].add(u)

    F = set()
    F_adj = [set() for _ in range(N + 1)]

    def add_edge(u, v):
        key = (min(u, v), max(u, v))
        if key not in F:
            F.add(key)
            F_adj[u].add(v)
            F_adj[v].add(u)

    for _ in range(K):
        visited = [False] * (N + 1)
        weight = [0] * (N + 1)
        order = []
        start = 1
        visited[start] = True
        order.append(start)
        for w in F_adj[start]:
            weight[w] += 1

        for _ in range(N - 1):
            u = -1
            for v in range(1, N + 1):
                if not visited[v]:
                    if u == -1 or weight[v] > weight[u]:
                        u = v
            visited[u] = True
            order.append(u)

            prev_visited_neighbors = [w for w in order[:-1] if w in orig_adj[u]]
            if prev_visited_neighbors:
                chosen = None
                if len(order) >= 2 and order[-2] in orig_adj[u]:
                    key = (min(u, order[-2]), max(u, order[-2]))
                    if key not in F:
                        chosen = order[-2]
                if chosen is None:
                    for w in reversed(prev_visited_neighbors):
                        key = (min(u, w), max(u, w))
                        if key not in F:
                            chosen = w
                            break
                if chosen is not None:
                    add_edge(u, chosen)

            for w in F_adj[u]:
                weight[w] += 1

    print(len(F))

main()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: 構築した証明書$F$上で実際に大域最小カット（Stoer-Wagner法）を計算し、元のグラフの最小カットが$K$以下であれば証明書上でも同じ値になることを実験的に確認せよ。
• 次回予告: メトリック閉包上のSteiner Tree 2-近似アルゴリズム

自己評価

自分の回答

気づき・メモ