[question linked]

谈恋爱

题目描述

有 ai 个男生， 编号 1,,,a，和 bi 个女生，编号 1,,,b。

第 ui个男生想和第 vi个女生谈恋爱。

在女生都愿意的情况下最多出现几对情侣。

输入描述

第 1 行为 a,b,m

接下来的 m 行每行包含两个正整数 u,v ，保证 1≤u≤a,1≤v≤b 。

1≤a,b≤500，1≤m≤250000。

输出描述

一个整数，表示最多产生多少对情侣。

输入输出样例

示例 1

输入

1
2
3
4
2 2 3
1 1
1 2
2 1

输出

1
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000; // 增大数组容量
const int M = 250010;

int n1, n2, m;
int e[M], ne[M], h[N], idx;
int match[N]; // 记录右边点匹配的左边点
bool st[N];   // 访问标记

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool find(int x) {
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i]; // 遍历右边的点
        if (!st[j]) {
            st[j] = true;
            // 右边点未匹配 或 原匹配点可找到新路径
            if (!match[j] || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h); // 初始化邻接表头指针，很重要
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b); // 将右边点编号映射到独立区间
    }

    int res = 0;
    for (int i = 1; i <= n1; i++) {
        memset(st, 0, sizeof st); // 每次重置访问标记
        if (find(i)) res++;
    }
    cout << res;
    return 0;
}