Overview

This problem involves pairing \(N\) “time slots” with \(M\) “part-time worker candidates” based on given conditions (whether they can work or not). Under the constraints that each time slot can be assigned at most 1 person, and each candidate can be assigned to at most 1 time slot, we need to find the maximum number of pairs that can be formed.

This can be solved as a problem of finding the maximum value of “Maximum Bipartite Matching” in graph theory.

Analysis

1. Organizing as a Bipartite Graph

Organizing this problem, we can divide it into the following 2 groups: - Group A: Time slots \(1, 2, \ldots, N\) - Group B: Candidates \(1, 2, \ldots, M\)

If we consider the condition “candidate \(j\) can work in time slot \(i\)” as an “edge” connecting node \(i\) in Group A and node \(j\) in Group B, this graph becomes a bipartite graph where edges exist only between different groups.

2. Why Doesn’t a Simple “First-Come, First-Served” Approach Work?

For example, consider the following case: - Time slot 1: Candidate A and Candidate B can work - Time slot 2: Only Candidate A can work

If we assign Candidate A to time slot 1 on a “first-come, first-served” basis, no one can be assigned to time slot 2, resulting in a total of 1 pair. However, if we assign Candidate B to time slot 1 and Candidate A to time slot 2, we can increase the total to 2 pairs.

Like this, the choice for one time slot can eliminate choices for other time slots, so finding the optimal combination requires a mechanism to “adjust assignments afterwards.”

Algorithm

To solve the maximum bipartite matching, we use an algorithm that searches for augmenting paths (a method using DFS).

1. Initialization: Set all time slots and candidates to an unassigned state.
2. Matching Attempt: For each time slot \(i = 1 \ldots N\), attempt assignment using the following procedure.
3. Search via DFS (Depth-First Search):
   • Check each candidate \(v\) who can work in time slot \(i\) one by one.
   • If candidate \(v\) is not yet assigned to anyone, immediately pair \(i\) and \(v\).
   • If candidate \(v\) is already assigned to another time slot \(i'\), recursively search whether “time slot \(i'\) can be reassigned to a different candidate other than \(v\).”
   • If reassignment is possible, assign the freed candidate \(v\) to time slot \(i\). This is called “finding an augmenting path.”
4. Counting: Each time an augmenting path is found, increment the matching count by 1.

This algorithm maximizes the total number of pairs by dissolving previously decided pairs when necessary and rearranging them into different pairs.

Complexity

• Time Complexity: \(O(N \times (N + E))\)
  • Here, \(E\) is the total number of “can work” relationships (number of edges).
  • A DFS is started from each time slot (\(N\) in total), and each DFS traverses at most all edges, resulting in this complexity. Under the given constraints (\(N, M \leq 100\)), this runs sufficiently fast.
• Space Complexity: \(O(N + M + E)\)
  • Memory is needed for the graph’s adjacency list and the array that holds the matching status.

Implementation Notes

• match array: By setting match[v] = u, we manage which time slot u candidate v is currently assigned to.

• visited array: Used to prevent checking the same candidate multiple times within a DFS starting from one time slot. This prevents infinite loops.

• Recursion depth: When \(N\) becomes large, sys.setrecursionlimit may be necessary, but since \(N=100\) in this problem, the default setting is sufficient.

  Source Code

import sys

# 再帰上限を増やす（念のため）
sys.setrecursionlimit(2000)

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    adj = []
    current = 2
    for _ in range(n):
        k = int(input_data[current])
        candidates = []
        for j in range(k):
            candidates.append(int(input_data[current + 1 + j]))
        adj.append(candidates)
        current += (k + 1)

    # 二部マッチングのための変数
    # match[v] は候補者 v がどの時間帯に割り当てられているかを保持する
    match = [-1] * (m + 1)
    
    def dfs(u, visited):
        """
        時間帯 u から始まる増加路を探す
        """
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                # 候補者 v がまだ誰にも割り当てられていないか、
                # 既に割り当てられている時間帯 match[v] に対して別の候補者を割り当て直せる場合
                if match[v] < 0 or dfs(match[v], visited):
                    match[v] = u
                    return True
        return False

    ans = 0
    for i in range(n):
        # 各時間帯についてマッチングを試みる
        visited = [False] * (m + 1)
        if dfs(i, visited):
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-preview.