HDU-2444 The Accomodation of Students【二分图判定/最大匹配】

题面链接
题意：
给你n个点，m条边，问你是否是二分图，如果是，找出最大匹配
思路：
邻接矩阵存图，对于每一条边，我们判断一下是否有第三个点使得这条边的两个端点在同一个环里，如果是，那么显然不可能构成二分图，在能够星形成二分图的情况下，用匈牙利跑一下最大匹配，无向图记得除以二就ok
AC代码;

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 222;

inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int g[maxn][maxn];//边的邻接矩阵
bool mk[233];
int n, m, link[233];

int dfs(int u) {
    for (int v = 1; v <= n; ++v)
        if (g[u][v] && !mk[v]) {
            mk[v] = 1;
            if (link[v] == -1 || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
    return 0;
}

int MaxMatch() {
    memset(link, -1, sizeof(link));
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        memset(mk, 0, sizeof(mk));
        if (dfs(i)) cnt++;
    }
    return cnt / 2;
}

int main() {
    while (cin >> n >> m) {
        int f = 1;
        memset(g, 0, sizeof(g));
        for (long long i = 0; i < m; i++) {
            int kk, jj;
            cin >> jj >> kk;
            if (f)
                for (int j = 1; j <= n; j++)
                    if (g[kk][j] && g[j][jj]) {
                        f = 0;
                        break;
                    }
            g[jj][kk] = g[kk][jj] = 1;
        }
        if (f) {
            int ans = MaxMatch();
            cout << ans << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}