Overview

We construct a bipartite graph consisting of time slots (left side) and candidates (right side), and the problem is to maximize the number of assignments under the constraint that “each candidate can only be used once.” This can be solved by finding the maximum bipartite matching.

Analysis

Key Observations

• The information “candidate \(c\) can be assigned to time slot \(i\)” can be viewed as “there is an edge \(i \to c\).”
• The constraints “at most one person per time slot” and “at most one slot per candidate” are exactly a matching (a set of edges sharing no endpoints) in a bipartite graph.
• Therefore, what we want is “the maximum number of edges we can select” = the size of the maximum matching.

Why Naive Approaches Fail

• Greedy (filling each time slot with any available candidate) fails.
  Example:
  
  • Time slot 1: candidates {1, 2}
    
  • Time slot 2: candidates {1}
    If we assign candidate 1 to time slot 1, time slot 2 cannot be filled, giving only 1 slot filled. However, assigning time slot 1→2 and time slot 2→1 fills 2 slots.
• Exhaustive search (trying all combinations of assignments) takes exponential time in the worst case.

Solution Approach

We use the idea of augmenting paths, which repeatedly “slightly rearranges the current assignment to increase the number of assignments by 1.”
A well-known method for efficiently finding augmenting paths is the Hopcroft–Karp algorithm.

Algorithm

Building the Bipartite Graph

• Left vertices: time slots \(0 \ldots N-1\)
• Right vertices: candidates \(0 \ldots M-1\)
• For each “time slot \(i\) can choose candidate \(c\)” in the input, we add an edge \(i \to c\) (in the code, we append the candidate number to adj[i]).

Hopcroft–Karp Algorithm (Maximum Bipartite Matching)

This speeds things up by finding multiple augmenting paths at once.

• pair_u[u]: the right vertex that left vertex \(u\) is matched to (-1 if unmatched)
• pair_v[v]: the left vertex that right vertex \(v\) is matched to (-1 if unmatched)

The procedure is as follows:

1. BFS (Building the Layer Structure)

   • Starting from unmatched left vertices (unassigned time slots), perform a breadth-first search.
   • Explore reachability by alternating “matched edge → unmatched edge → matched edge → …” and build the distance array dist.
   • If an unmatched right vertex is reached somewhere, an “augmenting path exists,” so proceed to the next step.

2. DFS (Augmenting Path Search Along Layers)

   • Perform DFS without violating the layer structure built by BFS (where dist increases by 1 at each step) to actually find augmenting paths.
   • Each time an augmenting path is found, flip “matched/unmatched” along the path, increasing the matching size by 1.

3. Repeat steps 1–2 until BFS finds no more augmenting paths, and output the final matching size as the answer.

In this problem, “the number of time slots that can be filled” = “the number of matched left vertices” = “the size of the matching,” so we simply output the maximum matching.

Complexity

• Time complexity: \(O(E\sqrt{V})\)
  where \(V = N + M\) and \(E = \sum_{i=1}^{N} K_i\) (the total number of edges).
• Space complexity: \(O(V + E)\) (for the adjacency list, matching arrays, etc.)

Implementation Notes

• 0-indexing: Since candidate numbers in the input are \(1 \ldots M\), the code subtracts 1 to convert them to \(0 \ldots M-1\).

• Adjacency list adj: adj[i] lists the “candidates (right vertices) that time slot i can choose.”

• BFS for augmenting path existence check: In Hopcroft–Karp, the key is to use BFS to determine “whether an unmatched right vertex is reachable (found),” and only run DFS when a reachable layer exists.

• Setting the distance of failed vertices to INF in DFS: By setting dist[u] = INF, we prevent wasting time by repeatedly exploring the same vertex.

  Source Code

import sys
from collections import deque

def hopcroft_karp(adj, n_left, n_right):
    INF = 10**9
    pair_u = [-1] * n_left
    pair_v = [-1] * n_right
    dist = [0] * n_left

    def bfs():
        q = deque()
        for u in range(n_left):
            if pair_u[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = INF

        found = False
        while q:
            u = q.popleft()
            for v in adj[u]:
                pu = pair_v[v]
                if pu != -1 and dist[pu] == INF:
                    dist[pu] = dist[u] + 1
                    q.append(pu)
                elif pu == -1:
                    found = True
        return found

    def dfs(u):
        for v in adj[u]:
            pu = pair_v[v]
            if pu == -1 or (dist[pu] == dist[u] + 1 and dfs(pu)):
                pair_u[u] = v
                pair_v[v] = u
                return True
        dist[u] = INF
        return False

    matching = 0
    while bfs():
        for u in range(n_left):
            if pair_u[u] == -1 and dfs(u):
                matching += 1
    return matching

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    adj = [[] for _ in range(N)]
    for i in range(N):
        Ki = next(it)
        for _ in range(Ki):
            c = next(it) - 1
            if 0 <= c < M:
                adj[i].append(c)

    ans = hopcroft_karp(adj, N, M)
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.