Overview

Given a bipartite graph, this problem asks for the minimum number of vertices to select such that at least one endpoint of every edge is selected. This is the “Minimum Vertex Cover Problem” in graph theory, and for bipartite graphs, it can be reduced to the “Maximum Matching Problem” to solve.

Analysis

The condition stated in the problem — “for every corridor (edge), at least one of the two buildings at its endpoints has an access point installed (vertex selected)” — is known in graph theory as a Vertex Cover. What we want to find is the minimum number of buildings to select, i.e., the size of the minimum vertex cover.

Finding the minimum vertex cover on a general graph is known to be computationally very expensive (NP-hard). However, the problem provides the powerful condition that “the graph is bipartite.”

For bipartite graphs, a famous theorem known as Kőnig’s theorem holds. It states: “The size of the minimum vertex cover in a bipartite graph = the size of the maximum matching.”

A matching is “a set of edges that do not share any endpoints.” In other words, this problem can be rephrased as the maximum matching problem: “Given a bipartite graph, what is the maximum number of edges that can be selected such that no two selected edges share an endpoint?”

Algorithm

To efficiently find the maximum matching of a bipartite graph, we use the Hopcroft-Karp algorithm. The procedure is as follows:

1. Partitioning the vertex set (coloring) First, we divide the vertices of the graph into two groups: “educational buildings” and “research buildings.” Since the graph is not necessarily connected, whenever we find an unvisited vertex, we perform BFS (breadth-first search) from it and alternately color vertices with \(0\) and \(1\). Let \(U\) be the set of vertices colored \(0\).

2. Running the Hopcroft-Karp algorithm Starting from the current matching state, we search for paths that can increase the number of matchings (augmenting paths).

   • BFS phase: Using all unmatched vertices on the \(U\) side as starting points, we explore alternating paths (paths that alternately traverse unmatched edges and matched edges) and record the shortest distance to unmatched vertices on the opposite side.
   • DFS phase: Following the shortest distances found by BFS, we traverse the graph to find paths that actually augment the matching. When found, we update the matching state.

We repeat these BFS and DFS phases until no more augmenting paths are found. The size of the final matching is the size of the minimum vertex cover (the answer).

Complexity

• Time complexity: \(O(M \sqrt{N})\) The Hopcroft-Karp algorithm takes \(O(M)\) time per BFS and DFS phase, and it has been proven that the number of phase repetitions is at most \(O(\sqrt{N})\). Therefore, the overall time complexity is \(O(M \sqrt{N})\), which comfortably fits within the time limit even under the constraints \(N, M \le 10^5\).
• Space complexity: \(O(N + M)\) We use adjacency lists to represent the graph, as well as arrays to record each vertex’s color, matching partner, and distance, consuming memory proportional to \(N\) and \(M\).

Implementation Notes

• Raising the recursion limit: When implementing DFS as a recursive function in Python, to prevent RecursionError due to excessive recursion depth, we raise the recursion limit using sys.setrecursionlimit at the beginning of the program.

• Skipping already-explored edges (constant factor optimization): In the DFS, we use an array called ptr. This records “how far along the edges from a vertex \(u\) we have already explored.” This prevents the waste of repeatedly exploring paths that have already been found to be dead ends, thereby guaranteeing the time complexity.

• Handling disconnected graphs: Since the problem states “the graph is not necessarily connected,” during the initial grouping (coloring), we check whether each vertex \(1 \dots N\) is unvisited (color not yet assigned), and if so, start a search from that vertex.

  Source Code

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

This editorial was generated by gemini-3.1-pro-thinking.