Overview

This is a problem of finding the minimum number of vertices to select in a bipartite graph such that every edge is “covered” by at least one of its endpoints (minimum vertex cover). By König’s theorem, the minimum vertex cover of a bipartite graph equals the maximum matching, so the answer can be obtained by finding the maximum matching.

Analysis

Problem Reformulation

The condition “for every corridor, at least one of the buildings at its endpoints has an access point installed” is exactly the Minimum Vertex Cover in graph theory terms.

Issues with a Naive Approach

Minimum vertex cover is NP-hard for general graphs, but this problem has the crucial condition that “the graph is bipartite.”

König’s Theorem

In a bipartite graph, the following equality holds:

\[\text{Size of minimum vertex cover} = \text{Size of maximum matching}\]

This is a property specific to bipartite graphs and does not hold for general graphs.

Concrete example: Consider buildings \(\{1, 2, 3, 4\}\) with edges \((1,3), (1,4), (2,3)\). Let the left side be \(\{1, 2\}\) (educational buildings) and the right side be \(\{3, 4\}\) (research buildings). The maximum matching is, for example, \(\{(1,4), (2,3)\}\) with \(2\) edges. The corresponding minimum vertex cover size is also \(2\) (for example, choosing \(\{1, 3\}\) covers all edges).

Strategy

1. Color the graph with 2 colors to determine the left and right vertex sets
2. Find the maximum matching of the bipartite graph
3. Output that value

Algorithm

Step 1: Bipartite Graph Coloring

Using BFS, color each connected component with 2 colors (color \(0\) and color \(1\)). Adjacent vertices are assigned different colors. Since the problem guarantees the graph is bipartite, no contradiction will occur.

Step 2: Find Maximum Matching with Hopcroft-Karp Algorithm

The Hopcroft-Karp algorithm efficiently finds the maximum matching of a bipartite graph.

1. BFS Phase: Perform BFS from unmatched left-side vertices to check for the existence of augmenting paths (paths that alternately traverse edges not in the matching → edges in the matching → …, reaching an unmatched right-side vertex), and assign distance labels.
2. DFS Phase: Following the distance labels, perform DFS from each unmatched left vertex to find augmenting paths and update the matching.
3. Repeat until no augmenting paths are found by BFS.

Since all shortest augmenting paths are processed simultaneously in each iteration, the number of iterations is bounded by \(O(\sqrt{V})\).

Step 3: Output

Output the size of the maximum matching = the size of the minimum vertex cover.

Complexity

• Time complexity: \(O(\sqrt{N} \cdot M)\) (complexity of the Hopcroft-Karp algorithm. BFS/DFS iterations are \(O(\sqrt{N})\) times, with all edges traversed in each iteration)
• Space complexity: \(O(N + M)\) (adjacency list, matching arrays, BFS queue, etc.)

Implementation Notes

• Bipartite coloring: Don’t forget to handle isolated vertices (buildings with no edges). Isolated vertices can be assigned either color and do not affect the matching.

• Recursion depth: When implementing DFS recursively, since \(N\) can be up to \(10^5\), be careful of stack overflow and set sys.setrecursionlimit appropriately.

• Distance dictionary management: Vertices for which no augmenting path was found during DFS should be removed from the dictionary to prevent redundant exploration of the same vertex (this is key to the efficiency of Hopcroft-Karp).

• When the graph is disconnected: You could find the maximum matching independently for each connected component, but applying Hopcroft-Karp to the entire graph handles this naturally.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.