定义

• 二分图：如果一个图的所有顶点可以被分为x和y两个集合，并且所有边的两个顶点恰好一个属于x，一个属于y，即每个集合内的顶点没有边相连。

实现

#include<stdio.h>
#include <iostream>
#include<cmath>
#include <cctype>
#include <cstdlib>
#include<cstring>
#include<algorithm>
#include <vector>
#include<queue>

using namespace std;
#define ll long long
#define il inline
#define oo (2147000000)
#define sc(x) scanf("%d",&x)
#define scc(x, y) scanf("%d%d",&x,&y)
#define sccc(x, y, z) scanf("%d%d%d",&x,&y,&z)
#define p(x) printf("%d\n",x)
#define m(x, y) ((x+y)>>1)
#define l(x) (x<<1)
#define r(x) (x<<1|1)
const int maxn = 1e5 + 6;

int n, m, a[101][101], match[101], book[101];

int dfs(int u) {
    int i;
    for (i = 1; i <= n; i++) {
        if (book[i] == 0 && a[u][i] == 1) {
            book[i] = 1;
            if (match[i] == 0 || dfs(match[i])) {
                match[i] = u;
                match[u] = i;
                return 1;
            }
        }
    }
    return 0;
}


int main() {
    int i, j, s, e, sum = 0;
    scc(n, m);
    for (i = 1; i <= m; i++) {
        scc(s, e);
        a[s][e] = a[e][s] = 1;
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) book[j] = 0;
        if (dfs(i)) sum++;
    }

    p(sum);
    return 0;
}