染色法判别二分图

    二分图最大匹配（匈牙利算法 O(nm)）

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N = 505, M = 1e5+5;
    4. int n1, n2, m, idx;
    5. int h[N], e[M], ne[M];
    6. int match[N];
    7. bool st[N];
    8. void add(int a, int b) {
    9.     e[idx] = b;
    10.     ne[idx] = h[a];
    11.     h[a] = idx++;
    12. }
    13. bool find(int x) {
    14.     for (int i = h[x]; i != -1; i = ne[i]) {
    15.         int j = e[i];
    16.         if (!st[j]) {
    17.             st[j] = 1;
    18.             if (!match[j] || find(match[j])) {
    19.                 match[j] = x;
    20.                 return 1;
    21.             }
    22.         }
    23.     }
    24.     return 0;
    25. }
    26. signed main() {
    27.     scanf("%d%d%d", &n1, &n2, &m);
    28.     memset(h, -1, sizeof h);
    29.     for (int i = 1; i <= m; i++) {
    30.         int u, v;
    31.         scanf("%d%d", &u, &v);
    32.         add(u, v);
    33.     }
    34.     int ans = 0;
    35.     for (int i = 1; i <= n1; i++) {
    36.         memset(st, 0, sizeof st);
    37.         if (find(i))
    38.             ans++;
    39.     }
    40.     cout << ans << '\n';
    41.     return 0;
    42. }