Overview

For every corridor (edge), we need to “place an access point in at least one of the two buildings at its endpoints.” We efficiently compute the minimum number of access points required, i.e., the size of the minimum vertex cover, by leveraging the properties of bipartite graphs.

Analysis

For each corridor \((u, v)\) to have Wi-Fi available, an access point must be placed at either \(u\) or \(v\). Viewing this as a graph problem:

• The set of buildings \(S\) where access points are placed must
• contain at least one endpoint of every edge

Thus, what we want to find is the size of the Minimum Vertex Cover.

However, finding the minimum vertex cover on a general graph is difficult (NP-hard). Naive approaches such as: - “Greedily select vertices with the largest degree” - “Pick one endpoint for each edge”

can easily deviate from the optimal solution and result in WA.

The key observation here is that, as stated in the problem, the graph is a bipartite graph. For bipartite graphs, the following famous theorem holds:

• König’s Theorem In a bipartite graph: $\(\text{Size of minimum vertex cover} = \text{Size of maximum matching}\)$

Therefore, this problem can be reduced to “finding the size of the maximum matching.” Additionally, since the input does not provide the bipartite partition (which side is the education building side and which is the research building side), we first perform 2-coloring to split vertices into left and right sets (starting from all vertices since the graph may not be connected).

Algorithm

1. 2-Coloring (Recovering the bipartite left-right partition)

   • For each connected component, assign colors 0/1 using DFS with a stack.
   • Edges always connect vertices of different colors (guaranteed by the input being a bipartite graph), so this gives us the left and right sets.
   • Vertices with color[u]==0 are treated as the left side (Left).

2. Maximum Matching (Hopcroft–Karp Algorithm)

   • Build a matching using only edges between left-side vertices \(U\) and right-side vertices \(V\).
   • The Hopcroft–Karp algorithm repeats the following:
     • BFS: Starting from unmatched left vertices, build layers (by distance) of vertices reachable via alternating paths (unmatched edge → matched edge → …), and find the length of the shortest augmenting path.
     • DFS: Following this layer structure, find as many shortest augmenting paths as possible that do not interfere with each other, and augment all of them at once.
   • When no more augmenting paths are found, we have the maximum matching.

3. Answer

   • By König’s theorem, the maximum matching size equals the minimum vertex cover size, so we output it directly.
   • (If there are 0 edges, the matching is 0, and the answer is also 0.)

Complexity

• Time complexity: \(O(M\sqrt{N})\) (Hopcroft–Karp algorithm, where \(M\) is the number of edges)
• Space complexity: \(O(N+M)\) (adjacency list, color array, matching arrays, etc.)

Implementation Notes

• Since the left-right partition is not given in the input, we must first perform 2-coloring (scanning all vertices to handle disconnected components).
• In Python, with \(N, M \le 10^5\), recursive DFS is prone to hitting the recursion limit, so in the code:
  • 2-coloring: Iterative DFS using a stack
  • DFS part of Hopcroft–Karp: Implemented iteratively (using a stack)

to ensure safety. - pairU[u] and pairV[v] manage the matched partners, and 0 is used as the sentinel (NIL) meaning “unmatched,” keeping the implementation concise.

Source Code

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()

---

This editorial was generated by gpt-5.2-high.