二分图的判断+二分图最大匹配数

使用黑白染色法进行判断，用HK算法高效计算最大匹配数
##代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int inf = 2e9;
const int max_n = 220;
const int max_m = 41000;
struct edge{
    int to, next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;E[cnt].next = head[from];
    head[from] = cnt++;
}
int color[max_n];
bool judge(int root) {
    queue<int> que;
    que.push(root);
    color[root] = 1;
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            int v = E[i].to;
            if (color[v] == color[u])return false;
            else if (color[v] == 0) {
                color[v] = -color[u];
                que.push(v);
            }
        }
    }return true;
}

int leftTo[max_n], rightTo[max_n];
int distleft[max_n], distright[max_n];
int dist;

bool seacherpath(int left_tot,int right_tot) {
    fill(distleft, distleft + left_tot + 1, -1);
    fill(distright, distright + right_tot + 1, -1);
    queue<int> que;dist = inf;
    for (int i = 1;i <= left_tot;++i)
        if (leftTo[i] == -1)
            que.push(i);
    while (!que.empty()) {
        int u = que.front();que.pop();
        if (distleft[u] > dist)break;
        for (int i = head[u];i;i = E[i].next) {
            int v = E[i].to;
            if (distright[v] != -1)continue;
            distright[v] = distleft[u] + 1;
            if (rightTo[v] == -1)dist = distright[v];
            else {
                distleft[rightTo[v]] = distright[v] + 1;
                que.push(rightTo[v]);
            }
        }
    }return dist != inf;
}
bool matchpath(int u) {
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (distright[v] != distleft[u] + 1)continue;
        if (distright[v] == dist && rightTo[v] != -1)continue;
        distright[v] = -1;
        if (rightTo[v] == -1 || matchpath(rightTo[v])) {
            leftTo[u] = v;
            rightTo[v] = u;
            return true;
        }
    }return false;
}

int HK(int left_tot,int right_tot) {
    fill(leftTo, leftTo + left_tot + 1, -1);
    fill(rightTo, rightTo + right_tot + 1, -1);
    int ans = 0;
    while (seacherpath(left_tot, right_tot)) {
        for (int i = 1;i <= left_tot;++i)
            if (leftTo[i] == -1 && matchpath(i))
                ++ans;
    }return ans;
}

int us[max_m], vs[max_m];
int N, M;
int main() {
    while (scanf("%d %d", &N, &M) != EOF) {
        fill(color, color + max_n, 0);
        fill(head, head + max_n, 0);cnt = 1;
        for (int i = 1;i <= M;++i) {
            scanf("%d %d", &us[i], &vs[i]);
            add(us[i], vs[i]);add(vs[i], us[i]);
        }bool flag = true;
        for (int i = 1;i <= N;++i) {
            if (color[i] == 0) {
                if (!judge(i)) {
                    flag = false;
                    break;
                }
            }
        }
        if (!flag)printf("No\n");
        else {
            int right_tot = 0;int left_tot = 0;
            for (int i = 1;i <= N;++i)
                if (color[i] == -1)color[i] = --right_tot;
                else color[i] = ++left_tot;
            fill(head, head + max_n, 0);cnt = 1;
            for (int i = 1;i <= M;++i) {
                if (color[us[i]] < 0)swap(us[i], vs[i]);
                add(color[us[i]], -color[vs[i]]);
            }printf("%d\n", HK(left_tot, -right_tot));
        }
    }
}