图
无向图
二分图
将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图
一个二分图当且仅当该图不含有奇数环
- 染色法判断二分图
二分图不一定是连通图。只要能将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图。
染色法
//dfs 版
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[2 * N], ne[2 * N], idx;
int color[N];
int n, m;
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool dfs(int u, int c){
color[u] = c; //先将该点染色
for (int i = h[u]; i != -1 ; i = ne[i]){
int j = e[i];
if (!color[j]){ //与该点相连的未染色的点染色
if (!dfs(j, 3 - c)) return false; //如果染成其他颜色失败，则说明图有有奇数环
}
else if (color[j] == color[u]) return false; //如果该点已经染为 c 色，则矛盾，图有奇数环
}
return true;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --){
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
int flag = true;
for (int i = 1; i <= n ; i ++){
if (!color[i]){
if (!dfs(i, 1)){ // 不一定是连通图，直接遍历起点
flag = false;
break;
}
}
}
if (flag) puts("Yes");
else puts("No");
return 0;
}
匈牙利算法二分图最大匹配
二分图的匹配，即一边的每一个点只能唯一地通过一条边连接另一边的唯一一个点(每一边连接的两点只被这条边连接)
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e5 + 5;
int h[N], e[M], ne[M], idx;
bool st[N];
int match[N];
int n1, n2, m;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool find(int u) {
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (st[j]) continue; // 该点已经考虑过，就跳过
st[j] = 1;
if (!match[j] || find(match[j])) { // 仅当另一边的某点没被匹配 或
// 它已匹配的同边点能替换匹配点，才匹配它
match[j] = u;
return 1;
}
}
return 0;
}
int main() {
cin >> n1 >> n2 >> m;
memset(h, -1, sizeof h);
while(m --) {
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
for (int i = 1; i <= n1; i ++) { // 从一边的角度出发
memset(st, 0, sizeof st);
if (find(i)) res ++;
}
cout << res << endl;
return 0;
}
最小生成树
最小生成树问题：从一个无向图中选出某些边，组成 权重和最小 且经过 所有点 的树。
这里的树和无向图图的区别：树不存在闭环，且所有边数等于点数减一
主要有两种算法：
- Prim
- kruscal
Prim
prim 和 dijkstra 的思想几乎是一致的，每次需要使用最小的边更新其他边，不同的是 prim 需要把离集合最近的点加入集合，因此更新距离时，不是更新出发点到某点的距离而是该点到集合的距离（讲人话就是更新边为某点到目前点的距离），当所有的点都加入集合时，完成选树，若某点无法连上，则建树失败。
步骤：
- scan（找到离集合最近的点）
- add（将该点加入集合）
- updata（更新距离数组）
复杂度：
- 时间：
- 空间：
- 稀疏图：
- 稠密图：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool st[N];
int n, m;
int prim(){
memset(dist, 0x3f, sizeof dist);
int sum = 0; //记录树的所有边长和
for (int i = 0 ; i < n ; i ++){ //每次循环都要找到一个点加入集合
int t = -1;
for (int j = 1 ; j <= n ; j ++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j; //选出未在集合中离集合最近的点
if (i && dist[t] == INF) return INF; //若出现无法连到某点的情况，说明无法建树，abandon
if (i) sum += dist[t];
st[t] = true; //把点加入集合
for (int j = 1 ; j <= n ; j ++)
dist[j] = min(dist[j], g[t][j]); //更新最新加入集合的点能到达的点的距离
}
return sum;
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m --){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c); //出现重边只存最小的
}
int t = prim();
if (t == INF) puts("impossible");
else cout << t << endl;
return 0;
}
Kruscal
kruscal 算法非常厉害，这很大可能得利于它基于了贪心的思想。kruscal 不需要使用复杂的数据结构存图，只需要将每条边的信息存下来，排序，再用并查集将树的边选出来即可，即按小到大的顺序选边，判断要选取的边是否构成闭环，构成则不选，不构成则选（当且仅当两个点未处于同一个集合中时说明无法构成闭环）。
路径压缩优化后的并查集单次插入查询时间复杂度为 O(1)，因此总时间复杂度最大取决于排序
复杂度：
- 时间：
- 空间：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int p[N];
struct Edge{
int a, b, w;
bool operator< (const Edge &T)const {
return w < T.w;
}
}e[M];
int n, m;
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 0 ; i < m ; i ++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
e[i] = {a, b, c}; //存边的信息
}
sort(e, e + m); //按边权重排序
for (int i = 1 ; i <= n ; i ++) p[i] = i; //初始化并查集
int res = 0 , cnt = 0; //记录树所有边长和，记录已选边数
for (int i = 0 ; i < m ; i ++) {
int a = e[i].a, b = e[i].b, w = e[i].w;
a = find(a), b = find(b);
if (a != b){ //若个点未连接过，连起来，记录边长
p[a] = b;
res += w;
cnt ++;
}
}
if (cnt < n - 1) puts("impossible"); //最终选边长小于 n - 1 说明有点没连上 abandon
else cout << res << endl;
return 0;
}