给定一个二分图，其左部点的个数为 𝑛 ，右部点的个数为 𝑚 ，边数为 𝑒 ，求其最大匹配的边数。 左部点从 1 至 𝑛 编号，右部点从 1 至 𝑚 编号。 输入 输入的第一行是三个整数，分别代表 𝑛 ， 𝑚 和 𝑒 。 接下来 𝑒 行，每行两个整数 𝑢 , 𝑣 ，表示存在一条连接左部点 𝑢 和右部点 𝑣 的边。 输出 输出一行一个整数，代表二分图最大匹配的边数。 样例输入 复制 1 1 1 1 1 样例输出 复制 1 提示 对于全部的测试点，保证： - 1 ≤ 𝑛 , 𝑚 ≤ 500 。 - 1 ≤ 𝑒 ≤ 5 × 10 4 。 - 1 ≤ 𝑢 ≤ 𝑛 ， 1 ≤ 𝑣 ≤ 𝑚 。

```python # 读取输入的 n, m, e n, m, e = map(int, input().split()) # 初始化邻接表 graph = [[] for _ in range(n + 1)] for _ in range(e): u, v = map(int, input().split()) graph[u].append(v) # 初始化匹配数组，用于记录右部点的匹配情况 match = [0] * (m + 1) # 初始化访问标记数组，用于避免重复访问 visited = [False] * (m + 1) # 匈牙利算法的核心函数，用于尝试为左部点 u 找到匹配 def find(u): for v in graph[u]: if not visited[v]: visited[v] = True if match[v] == 0 or find(match[v]): match[v] = u return True return False # 计算最大匹配的边数 ans = 0 for i in range(1, n + 1): visited = [False] * (m + 1) if find(i): ans += 1 # 输出最大匹配的边数 print(ans) ``` [2025-12-13 21:24:15 | AI问答 | 275点数解答]