概要

すべての通路（辺）について「両端のうち少なくとも一方の建物にアクセスポイントを置く」ための最小個数、つまり最小頂点被覆のサイズを、二部グラフの性質を使って高速に求めます。

考察

各通路 \((u, v)\) が Wi-Fi 利用可能であるためには、\(u\) または \(v\) のどちらかにアクセスポイントが必要です。これはグラフ問題として見ると、

• アクセスポイントを置く建物集合 \(S\) が
• すべての辺の少なくとも片方の端点を含む

という条件なので、求めたいのは 最小頂点被覆（Minimum Vertex Cover） のサイズです。

しかし一般のグラフで最小頂点被覆を求めるのは難しく（NP困難）、例えば - 「次数が大きい頂点から貪欲に選ぶ」 - 「辺ごとに片方を選ぶ」 のような素朴な方法は、簡単に最適解から外れて WA になります。

ここで重要な気づきは、問題文よりグラフが 二部グラフ であることです。二部グラフでは次の有名な定理が成り立ちます。

• Kőnig（ケーニグ）の定理
  二部グラフにおいて
  $\(\text{最小頂点被覆のサイズ} = \text{最大マッチングのサイズ}\)$

したがって、この問題は「最大マッチングのサイズを求めればよい」問題に変換できます。
また、入力では二部の分割（教育棟側・研究棟側）が与えられないので、まず 2 彩色して左右に分けます（グラフは連結でない可能性があるので全頂点から開始）。

アルゴリズム

1. 2 彩色（二部グラフの左右分割を復元）

   • 各連結成分ごとに DFS/スタックで色 0/1 を割り当てます。
   • 辺は必ず異なる色同士を結ぶ（入力が二部グラフであることが保証）ので、これで左右集合が得られます。
   • color[u]==0 を左側（Left）とします。

2. 最大マッチング（Hopcroft–Karp 法）

   • 左側頂点 \(U\) と右側頂点 \(V\) の間の辺だけを使ってマッチングを作ります。
   • Hopcroft–Karp 法は以下を繰り返します。
     • BFS：未マッチの左頂点から、交互路（未使用辺→使用辺→…）で到達できる範囲を層（距離）として構築し、最短の増加路の長さを探す
     • DFS：その層構造に沿って、互いに干渉しない最短増加路をできるだけ見つけて一気に増加させる
   • 増加路が見つからなくなったら最大マッチングです。

3. 答え

   • ケーニグの定理より、最大マッチング数が最小頂点被覆サイズに等しいので、そのまま出力します。
   • （辺が 0 本ならマッチングは 0、答えも 0 になります。）

計算量

• 時間計算量: \(O(M\sqrt{N})\)（Hopcroft–Karp 法。\(M\) は辺数）
• 空間計算量: \(O(N+M)\)（隣接リスト、色、マッチング配列など）

実装のポイント

• 左右分割が入力にないので、最初に必ず 2 彩色します（非連結にも対応するため全頂点を走査）。

• Python で \(N, M \le 10^5\) は再帰 DFS だと再帰上限に引っかかりやすいので、コードでは

  • 2 彩色：スタックによる反復 DFS
  • Hopcroft–Karp の DFS 部分：反復（スタック）で実装
    として安全にしています。

• pairU[u], pairV[v] によりマッチ先を管理し、0 を「未マッチ」の番兵（NIL）として扱うことで実装を簡潔にしています。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it); v = next(it)
        g[u].append(v)
        g[v].append(u)

    # 2-coloring to get bipartition
    color = [-1] * (N + 1)
    for s in range(1, N + 1):
        if color[s] != -1:
            continue
        color[s] = 0
        stack = [s]
        while stack:
            u = stack.pop()
            cu = color[u]
            for v in g[u]:
                if color[v] == -1:
                    color[v] = cu ^ 1
                    stack.append(v)

    left = [u for u in range(1, N + 1) if color[u] == 0]

    adjU = [[] for _ in range(N + 1)]
    for u in left:
        au = adjU[u]
        for v in g[u]:
            if color[v] == 1:
                au.append(v)

    pairU = [0] * (N + 1)
    pairV = [0] * (N + 1)
    dist = [0] * (N + 1)
    ptr = [0] * (N + 1)
    parentU = [0] * (N + 1)
    parentV = [0] * (N + 1)

    INF = 10**18

    def bfs():
        dq = deque()
        for u in left:
            if pairU[u] == 0:
                dist[u] = 0
                dq.append(u)
            else:
                dist[u] = INF

        dist_nil = INF
        while dq:
            u = dq.popleft()
            du = dist[u]
            if du >= dist_nil:
                continue
            for v in adjU[u]:
                pu = pairV[v]
                if pu == 0:
                    dist_nil = du + 1
                elif dist[pu] == INF:
                    dist[pu] = du + 1
                    dq.append(pu)
        return dist_nil != INF

    def dfs_iter(root):
        parentU[root] = 0
        stack = [root]
        while stack:
            u = stack[-1]
            au = adjU[u]
            i = ptr[u]
            advanced = False
            while i < len(au):
                v = au[i]
                i += 1
                ptr[u] = i
                pu = pairV[v]
                if pu == 0:
                    # Augment
                    curr_u = u
                    curr_v = v
                    while True:
                        pairU[curr_u] = curr_v
                        pairV[curr_v] = curr_u
                        prev_u = parentU[curr_u]
                        if prev_u == 0:
                            break
                        curr_v = parentV[curr_u]
                        curr_u = prev_u
                    return True
                if dist[pu] == dist[u] + 1:
                    parentU[pu] = u
                    parentV[pu] = v
                    stack.append(pu)
                    advanced = True
                    break
            if advanced:
                continue
            dist[u] = INF
            stack.pop()
        return False

    matching = 0
    while bfs():
        for u in left:
            ptr[u] = 0
        for u in left:
            if pairU[u] == 0 and dfs_iter(u):
                matching += 1

    print(matching)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。