この問題は最大流を用いて解くことができます。

建物を頂点、通路を辺とした二部グラフを考えることで、この問題は最小頂点被覆問題そのものになります。

二部グラフの最小頂点被覆の大きさは、最大マッチングの大きさと一致することが知られています（ケーニヒの定理（König’s theorem））。

二部グラフの最大マッチングは、ソースとシンクを適切に補ったネットワークにおける最大流と一致するため、 \(O(\sqrt{N}M)\)でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<int>> G(n);
  for(int i=0; i<m; i++){
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  vector<int>color(n, -1);
  for(int i=0; i<n; i++){
    if(color[i] == -1){
      queue<int>q({i});
      color[i] = 0;
      while(q.size() > 0){
        int v = q.front(); q.pop();
        for(int vv: G[v]){
          if(color[vv] == -1){
            color[vv] = color[v] ^ 1;
            q.push(vv);
          }
        }
      }
    }
  }

  atcoder::mf_graph<int> g(n+2);  // n: source, n+1: sink
  for(int v=0; v<n; v++){
    if(color[v] == 0){
      g.add_edge(n, v, 1);
      for(int vv: G[v]){
        if(color[vv] == 1){
          g.add_edge(v, vv, 1);
        }
      }
    }else{
      g.add_edge(v, n+1, 1);
    }
  }
  cout << g.flow(n, n+1) << endl;
}

実装例 (Python)

ACLを使う場合、実行時間制限が非常にタイトです。

from atcoder.maxflow import MFGraph

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  G[u].append(v)
  G[v].append(u)

color = [-1] * N
for i in range(N):
  if color[i] == -1:
    stack = [i]
    color[i] = 0
    while len(stack) > 0:
      v = stack.pop()
      for vv in G[v]:
        if color[vv] == -1:
          color[vv] = color[v] ^ 1
          stack.append(vv)

g = MFGraph(N+2)  # n: source, n+1: sink
for v in range(N):
  if color[v] == 0:
    g.add_edge(N, v, 1)
    for vv in G[v]:
      if color[vv] == 1:
        g.add_edge(v, vv, 1)
  else:
    g.add_edge(v, N+1, 1)

print(g.flow(N, N+1))

おまけ：ケーニヒの定理の略証

最大マッチングのサイズを \(m\) 、最小頂点被覆のサイズを \(c\) とする。

\(m \leq c\) であること

最大マッチング \(M\) と最小頂点被覆 \(C\) を任意の取る。\(C\) は頂点被覆なので、\(M\) に属する各辺の両端の少なくとも一方は \(C\) に属する。そこで、\(M\) に属する辺 \(e\) に対し、\(e\) の端点かつ \(C\) に属する頂点を対応させる写像 \(f:M\to C\) を考える。\(M\) はマッチングなので頂点を共有しておらず、\(f\) は単射になる。よって \(m \leq c\) である。

\( m\geq c\) であること

サイズ \(m\) の頂点被覆を構築する。与えられた二部グラフ \(G\) の部集合を \(A,B\) とし、次のようなネットワークグラフ \(G'\) を考える。

• 頂点集合は \(A\cup B \cup\{s,t\}\)
• \(G\) の各辺 \(e=(u,v)\) に対し、容量 \(\infty\) の辺 \((u,v)\) を張る
• \(A\) の各頂点 \(a\) に対し、容量 \(1\) の辺 \((s,a)\) を張る
• \(B\) の各頂点 \(b\) に対し、容量 \(1\) の辺 \((b,t)\) を張る

\(G\) の最大マッチングの大きさ \(m\) は \(G'\) の s-t 最大流のサイズに等しい。また、最大フロー最小カット定理より、\(G'\) の s-t 最大流のサイズは \(G'\) の s-t 最小カットのサイズに等しい。

\(G'\) の s-t 最小カットを \((S,T)\) とし、\(A_S=A\cap S\) と定める。同様に \(A_T,B_S,B_T\) を定める。 \(G\) の辺容量は \(\infty\) であるから、最小カットは \(G\) の辺を含まず、 \(A_S\) と \(B_T\) の間に辺はない。よって s-t 最小カットのサイズは \(|A_T|+|B_S|\) となる。一方、\(A_S\) と \(B_T\) 間に辺はないことから、\(G\) の辺は全て \(A_T \cup B_S\) を端点に持ち、これは \(G\) の頂点被覆である。よって \(m=|A_T|+|B_S|=|A_T\cup B_S|\geq c\) である。

参考：wikipedia