概要

二部グラフにおいて、すべての辺を少なくとも一方の端点で「カバー」するために選ぶ頂点数の最小値（最小頂点被覆）を求める問題です。ケーニヒの定理により、二部グラフの最小頂点被覆は最大マッチングに等しいため、最大マッチングを求めれば答えが得られます。

考察

問題の言い換え

「すべての連絡通路について、その両端の建物のうち少なくとも一方にアクセスポイントが設置されている」という条件は、グラフ理論でいう 最小頂点被覆（Minimum Vertex Cover） そのものです。

素朴なアプローチの問題点

最小頂点被覆は一般のグラフでは NP 困難ですが、この問題では「グラフは二部グラフである」という重要な条件があります。

ケーニヒの定理（König’s theorem）

二部グラフにおいて、次の等式が成り立ちます：

\[\text{最小頂点被覆のサイズ} = \text{最大マッチングのサイズ}\]

これは二部グラフ特有の性質であり、一般のグラフでは成り立ちません。

具体例: 建物が \(\{1, 2, 3, 4\}\) で、辺が \((1,3), (1,4), (2,3)\) の場合を考えます。二部グラフの左側を \(\{1, 2\}\)（教育棟）、右側を \(\{3, 4\}\)（研究棟）とすると、最大マッチングは例えば \(\{(1,4), (2,3)\}\) の \(2\) 本です。対応する最小頂点被覆のサイズも \(2\)（例えば \(\{1, 3\}\) を選べば全辺をカバー）となります。

方針

1. グラフを 2 色で彩色し、左側・右側の頂点集合を決定する
2. 二部グラフの最大マッチングを求める
3. その値を出力する

アルゴリズム

ステップ 1: 二部グラフの彩色

BFS を用いて各連結成分を 2 色（色 \(0\) と色 \(1\)）で塗り分けます。隣接する頂点には異なる色を割り当てます。問題文でグラフが二部グラフであることが保証されているため、矛盾は起きません。

ステップ 2: Hopcroft-Karp 法で最大マッチングを求める

Hopcroft-Karp 法は二部グラフの最大マッチングを効率的に求めるアルゴリズムです。

1. BFS フェーズ: 左側のマッチングされていない頂点から BFS を行い、増加パス（マッチングに含まれない辺→含まれる辺→…と交互に辿り、マッチングされていない右側頂点に到達するパス）の存在を確認し、距離ラベルを付与します。
2. DFS フェーズ: 距離ラベルに従って各未マッチング左頂点から DFS を行い、増加パスを見つけてマッチングを更新します。
3. BFS で増加パスが見つからなくなるまで繰り返します。

各反復で最短の増加パスをすべて同時に処理するため、反復回数が \(O(\sqrt{V})\) 回で済みます。

ステップ 3: 出力

最大マッチングのサイズ = 最小頂点被覆のサイズを出力します。

計算量

• 時間計算量: \(O(\sqrt{N} \cdot M)\)（Hopcroft-Karp 法の計算量。BFS/DFS の反復が \(O(\sqrt{N})\) 回、各反復で全辺を走査）
• 空間計算量: \(O(N + M)\)（隣接リスト、マッチング配列、BFS 用のキューなど）

実装のポイント

• 二部彩色: 孤立頂点（辺を持たない建物）も忘れずに処理します。孤立頂点はどちらの色でもよく、マッチングにも影響しません。

• 再帰の深さ: DFS を再帰で実装する場合、\(N\) が最大 \(10^5\) なのでスタックオーバーフローに注意し、sys.setrecursionlimit を適切に設定します。

• 距離辞書の管理: DFS で増加パスが見つからなかった頂点は辞書から削除することで、同じ頂点を重複して探索することを防ぎます（これが Hopcroft-Karp の効率性の鍵です）。

• グラフが非連結の場合: 各連結成分ごとに独立に最大マッチングを求めても良いですが、Hopcroft-Karp をグラフ全体に適用すれば自然に処理されます。

  ソースコード

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for i in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    # This is minimum vertex cover on a bipartite graph.
    # By König's theorem, min vertex cover = max matching in bipartite graph.
    # We need to find maximum matching using Hopcroft-Karp.
    
    # First, 2-color the graph (it's bipartite)
    color = [-1] * (N + 1)
    # left_nodes: color 0, right_nodes: color 1
    
    for start in range(1, N + 1):
        if color[start] != -1:
            continue
        if not adj[start]:
            color[start] = 0
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
    
    # Build bipartite graph: left = color 0 nodes, right = color 1 nodes
    # Hopcroft-Karp
    # For each left node, store its neighbors (right nodes)
    
    left_nodes = []
    right_nodes = []
    for i in range(1, N + 1):
        if color[i] == 0:
            left_nodes.append(i)
        else:
            right_nodes.append(i)
    
    # match_left[u] = matched right node (or -1)
    # match_right[v] = matched left node (or -1)
    match_left = [-1] * (N + 1)
    match_right = [-1] * (N + 1)
    
    def bfs():
        dist = {}
        queue = deque()
        for u in left_nodes:
            if match_left[u] == -1:
                dist[u] = 0
                queue.append(u)
        
        found = False
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                next_u = match_right[v]
                if next_u == -1:
                    found = True
                elif next_u not in dist:
                    dist[next_u] = dist[u] + 1
                    queue.append(next_u)
        
        return found, dist
    
    def dfs(u, dist):
        for v in adj[u]:
            next_u = match_right[v]
            if next_u == -1 or (next_u in dist and dist[next_u] == dist[u] + 1 and dfs(next_u, dist)):
                match_left[u] = v
                match_right[v] = u
                del dist[u]
                return True
        
        del dist[u]
        return False
    
    # Hopcroft-Karp with iterative DFS to avoid recursion limit
    def dfs_iterative(start, dist):
        # We need to find augmenting path from start
        # Stack-based DFS with backtracking
        stack = [(start, iter(adj[start]))]
        path = [start]
        
        while stack:
            u, it = stack[-1]
            found_next = False
            for v in it:
                next_u = match_right[v]
                if next_u == -1:
                    # Found augmenting path, augment along path
                    match_left[u] = v
                    match_right[v] = u
                    # Backtrack through path
                    for i in range(len(stack) - 2, -1, -1):
                        pu = stack[i][0]
                        pv = match_left[path[i + 1]] if i + 1 < len(path) else None
                        # Actually, let me just use the recursive version with increased limit
                    # This is getting complicated, let's use recursive with sys.setrecursionlimit
                    return True  # placeholder
                elif next_u in dist and dist[next_u] == dist[u] + 1:
                    stack.append((next_u, iter(adj[next_u])))
                    path.append(next_u)
                    found_next = True
                    break
            if not found_next:
                dist.pop(u, None)
                stack.pop()
                path.pop()
        return False
    
    sys.setrecursionlimit(200000)
    
    matching = 0
    while True:
        found, dist = bfs()
        if not found:
            break
        for u in left_nodes:
            if match_left[u] == -1 and u in dist:
                if dfs(u, dist):
                    matching += 1
    
    print(matching)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。