概要

与えられた二部グラフにおいて、すべての辺の少なくとも一方の端点を選ぶ最小頂点数を求める問題です。これはグラフ理論における「最小頂点被覆問題」であり、二部グラフの性質を利用して「最大マッチング問題」に帰着して解くことができます。

考察

問題文の条件「すべての連絡通路（辺）について、その両端の建物のうち少なくとも一方にアクセスポイントが設置（頂点を選択）されている」という状態は、グラフ理論において頂点被覆（Vertex Cover）と呼ばれます。 今回求めたいのは、選ぶ建物の数の最小値、すなわち最小頂点被覆のサイズです。

一般のグラフにおいて最小頂点被覆を求める問題は非常に計算時間がかかる（NP困難）ことが知られています。しかし、問題文に「グラフは二部グラフである」という強力な条件が与えられています。

二部グラフにおいては、ケーニヒの定理（Kőnig’s theorem）という有名な定理が成り立ちます。これは、 「二部グラフにおける最小頂点被覆のサイズ ＝ 最大マッチングのサイズ」 というものです。

マッチングとは、「互いに端点を共有しない辺の集合」のことです。つまり、この問題は「与えられた二部グラフから、端点を共有しないように最大で何本の辺を選べるか」という最大マッチング問題に言い換えることができます。

アルゴリズム

二部グラフの最大マッチングを高速に求めるために、Hopcroft-Karp（ホップクロフト・カープ）アルゴリズムを使用します。手順は以下の通りです。

1. 頂点集合の分割（彩色） まずはグラフの頂点を「教育棟」と「研究棟」の2つのグループに分けます。グラフは連結とは限らないため、未訪問の頂点を見つけるたびにそこからBFS（幅優先探索）を行い、頂点に \(0\) と \(1\) の色を交互に塗っていきます。色 \(0\) の頂点集合を \(U\) とします。

2. Hopcroft-Karpアルゴリズムの実行 現在のマッチング状態から、マッチングの数を増やせるパス（増加パス）を探します。

   • BFSフェーズ: 未マッチの \(U\) 側の頂点をすべて始点とし、交互道（マッチしていない辺とマッチしている辺を交互に通るパス）を探索して、未マッチの反対側の頂点までの最短距離を記録します。
   • DFSフェーズ: BFSで求めた最短距離の通りにグラフをたどり、実際にマッチングを増加させるパスを見つけます。見つけたらマッチング状態を更新します。

この BFS と DFS のフェーズを、増加パスが見つからなくなるまで繰り返します。最終的なマッチングのサイズが、求める最小頂点被覆のサイズ（答え）となります。

計算量

• 時間計算量: \(O(M \sqrt{N})\) Hopcroft-Karpアルゴリズムは、1回のBFSとDFSのフェーズで \(O(M)\) の時間がかかり、フェーズの繰り返し回数が最大でも \(O(\sqrt{N})\) 回で済むことが証明されています。したがって全体の時間計算量は \(O(M \sqrt{N})\) となり、\(N, M \le 10^5\) の制約下でも余裕で実行時間制限に間に合います。
• 空間計算量: \(O(N + M)\) グラフを表現するための隣接リストや、各頂点の色・マッチング相手・距離を記録する配列などを使用するため、\(N\) と \(M\) に比例するメモリを消費します。

実装のポイント

• 再帰上限の引き上げ: PythonでDFSを再帰関数として実装する場合、再帰が深くなりすぎて RecursionError になるのを防ぐため、プログラムの冒頭で sys.setrecursionlimit を用いて再帰上限を引き上げています。

• 探索済みの辺のスキップ（定数倍高速化）: DFSの中で ptr という配列を使用しています。これは「ある頂点 \(u\) から出る辺のうち、どこまで探索したか」を記憶しておくためのものです。これにより、一度探索してダメだった経路を何度も探索する無駄を防ぎ、計算量を保証しています。

• 非連結グラフへの対応: 問題文に「グラフは連結とは限らない」とあるため、最初のグループ分け（彩色）の際に、すべての頂点 \(1 \dots N\) について未訪問（色が未設定）かどうかを確認し、未訪問であればそこを始点に探索を開始する処理を入れています。

  ソースコード

import sys

sys.setrecursionlimit(200000)

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    
    adj = [[] for _ in range(N + 1)]
    idx = 2
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx+1])
        adj[u].append(v)
        adj[v].append(u)
        idx += 2
        
    color = [-1] * (N + 1)
    U = []
    
    q = [0] * (N + 1)
    for i in range(1, N + 1):
        if color[i] == -1:
            color[i] = 0
            U.append(i)
            
            head_q = 0
            tail_q = 0
            q[tail_q] = i
            tail_q += 1
            
            while head_q < tail_q:
                u = q[head_q]
                head_q += 1
                for v in adj[u]:
                    if color[v] == -1:
                        color[v] = 1 - color[u]
                        if color[v] == 0:
                            U.append(v)
                        q[tail_q] = v
                        tail_q += 1

    match = [-1] * (N + 1)
    dist = [-1] * (N + 1)
    ptr = [0] * (N + 1)
    
    def bfs():
        head_q = 0
        tail_q = 0
        for u in U:
            if match[u] == -1:
                dist[u] = 0
                q[tail_q] = u
                tail_q += 1
            else:
                dist[u] = -1
        
        found = False
        while head_q < tail_q:
            u = q[head_q]
            head_q += 1
            for v in adj[u]:
                if match[v] == -1:
                    found = True
                elif dist[match[v]] == -1:
                    dist[match[v]] = dist[u] + 1
                    q[tail_q] = match[v]
                    tail_q += 1
        return found

    def dfs(u):
        edges = adj[u]
        while ptr[u] < len(edges):
            v = edges[ptr[u]]
            ptr[u] += 1
            if match[v] == -1 or (dist[match[v]] == dist[u] + 1 and dfs(match[v])):
                match[v] = u
                match[u] = v
                return True
        dist[u] = -1
        return False

    ans = 0
    while bfs():
        for i in range(1, N + 1):
            ptr[i] = 0
        for u in U:
            if match[u] == -1:
                if dfs(u):
                    ans += 1
                    
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。