1. 二分图的定义 一个图中的顶点可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。 2. 二分图的判定 一个不含环的图一定是二分图，如果有环则不存在奇数环的图一定是二分图 3. 判断二分图的两种算法 4. 染色法 算法思路：利用二分图的定义，把每个连通图中的每个相邻的点染成不同的颜色，如果每个相邻的点都满足颜色不同则是二分图，如果出现矛盾则不是二分图
例题：染色法判定二分图 给定一个n个点m条边的无向图，图中可能存在重边和自环。 请你判断这个图是否是二分图。
输入格式 第一行包含两个整数n和m。 接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。
输出格式 如果给定图是二分图，则输出“Yes”，否则输出“No”。
数据范围 1≤n,m≤105 输入样例： 4 4 1 3 1 4 2 3 2 4 输出样例： Yes
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 100010, M = 200010; int n, m; int h[N], e[M], ne[M], idx; int color[N]; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } // 深度优先搜索，把相邻的两个点染成不同的颜色 bool dfs(int u, int x) { color[u] = x; for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(!color[j]) // 如果没染过颜色，则用递归染与u不同的颜色 { if(!dfs(j, 3 - x) return false; } else if(color[j] == x) return false; // 如果染过颜色判断是否与u相同颜色 } return true; } int main() { cin >> n >> m; memset(h, -1, sizeof(h)); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); } bool flag = true; // 循环n次，保证每个点都染过颜色 for(int i = 1; i <= n; i++) { if(!color[i]) { if(!dfs(i, 1)) { flag = false; break; } } } if(flag) printf("Yes\n"); else printf("No\n"); return 0; }5. 匈牙利算法 算法思路：遍历左边所有的点，寻找右边与之匹配的点，如果右边的点未被匹配则与之匹配，如果右边的点已经与左边的点q匹配了，那么寻找q是否还可以和右边其他点进行匹配，如果可以就与之匹配，如果不行就寻找右边下一个点
例题： 二分图的最大匹配 给定一个二分图，其中左半部包含n1个点（编号1-n1），右半部包含n2个点（编号1-n2），二分图共包含m条边。 数据保证任意一条边的两个端点都不可能在同一部分中。 请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式 第一行包含三个整数 n1、 n2 和 m。 接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。
输出格式 输出一个整数，表示二分图的最大匹配数。
数据范围 1≤n1,n2≤500, 1≤u≤n1, 1≤v≤n2, 1≤m≤105 输入样例： 2 2 4 1 1 1 2 2 1 2 2 输出样例： 2
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 510, M = 100010; int n1, n2, m; int h[N], e[M], ne[M], idx; int match[N]; bool str[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 != -1; i = ne[i]) { int j = e[i]; if(!str[j]) // 确保每次只寻找右边未被寻找过的点 { str[j] = true; if(match[j] == 0 || find(match[j])) // 如果右边未匹配或者匹配后，与之匹配的左边的点还可以找到右边的另一个点匹配 { match[j] = x; // 使j与要找的点匹配 return true; } } } return false; } int main() { cin >> n1 >> n2 >> m; memset(h, -1, sizeof(h)); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; add(a, b); } int res = 0; for(int i = 1; i <= n1; i++) { memset(str, false, sizeof(str)); // 为了确保左边每次寻找右边时只寻找一遍，每次寻找前把右边初始化为未寻找过 if(find(i)) res++; // 如果找到匹配对象则结果加一 } printf("%d\n", res); return 0; }