算法基础课个人总结
OI-WiKi：
https://oi-wiki.org/
算法可视化：
https://visualgo.net/en
基本算法：
1.高精度：
1.1 高精度加法：
//逆序输入，逆序输出
vector<int> add(vector<int> A, vector<int> B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i++)
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(i % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
(1)高精度加法：
https://www.acwing.com/problem/content/793/
1.2 高精度减法：
//逆序输入，逆序输出
bool cmp(vector<int> A, vector<int> B)
{
if (A.size() != B.size()) return A.size() > B.size();
for (int i = A.size() - 1; i >= 0; i--)
{
if (A[i] != B[i])
return A[i] > B[i];
}
return true;
}
//需确保a大于b
vector<int> sub(vector<int> A, vector<int> B)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i++)
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0)
C.pop_back();
return C;
}
(1)高精度减法：
https://www.acwing.com/problem/content/794/
1.3 高精度乘法：
//逆序输入，逆序输出
//A*B
vector<int> mul(vector<int> A, vector<int> B)
{
vector<int> C(A.size() + B.size(), 0);
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < B.size(); j++)
c[i + j] = A[i] * B[j];
int t = 0;
for (int i = 0; i < C.size(); i++)
{
t += C[i];
C[i] = t % 10;
t /= 10;
}
while (C.size() > 1 && C.back() == 0)
C.pop_back();
return C;
}
//A*b
vector<int> mul(vector<int> A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i++)
{
t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (t)
{
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0)
C.pop_back();
return C;
}
(1)高精度乘法：
https://www.acwing.com/problem/content/795/
1.4 高精度除法：
//逆序输入，逆序输出
//r为余数
vector<int> div(vector<int> A, int b, int& r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i--)
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size > 1 && C.back() == 0)
C.pop_back();
return C;
}
(1)高精度除法：
https://www.acwing.com/problem/content/796/
2.二分：
思路：使用减治策略，不断二分查找范围，最终查找范围退化为一个点，即为查找对象
2.1 整数二分：
思路：依据条件函数的真假，可以将区间分为左右两个部分(也是使用二分的必要条件)，
LB可以找到第一个使条件为真的元素，RB可以找到最后一个使条件为真的元素
//返回[l,r]内第一个满足条件的元素
int LB(int l, int r, bool satisfied(int))
{
while (l < r)
{
int mid = l + r >> 1;
if (satisfied(a[mid])) r = mid;
else l = mid + 1;
}
return l;
}
//返回[l,r]内最后一个满足条件的元素
int RB(int l, int r, bool satisfied(int))
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (satisfied(a[mid])) l = mid;
else r = mid - 1;
}
return r;
}
时间：平均O(logn) 空间：O(1)
关于RB：用Li和Ri分别指代左边部分和右边部分的元素，经过数次二分后，查找范围最终会退化为仅含两个元素，一共三种情况：[Li,Ri],[Li,Li+1],[Ri,Ri+1]。对于RB，若求mid=l+r>>1，则会在[Li,Ri],[Li,Li+1]两种情况处出现死循环
(1)数的范围：
https://www.acwing.com/problem/content/791/
2.2 浮点数二分：
(1)数的三次方根：
https://www.acwing.com/problem/content/792/
3.位运算：
(1)二进制中1的个数：
https://www.acwing.com/problem/content/803/
lowbit操作：
//获得x二进制表示的最高位所表示的数，如6=110(2)，lowbit(6)=100(2)
lowbit(x) = x & (-x)
4.前缀和与差分：
4.1二维前缀和：
(1)子矩阵的和：
https://www.acwing.com/problem/content/798/
4.2 二维差分：
(1)差分矩阵：
https://www.acwing.com/problem/content/800/
5.排序：
5.1 快速排序：
5.2 归并排序：
5.3 堆排序：
5.4 冒泡排序：
5.5 插入排序：
5.6 选择排序：
6.贪心：
数据结构：
1.字符串匹配：
1.1 KMP：
int next[N];
string p, s;
//构建next数组
for (int i = 1, j = 0; i < p.size(); i++)
{
while (j && p[i] != p[j]) j = next[j];
if (p[i] == p[j]) j++;
next[i + 1] = j;
}
//比对
for (int i = 0, j = 0; i < s.size(); i++)
{
while (j && s[i] != p[j]) j = next[j];
if (s[i] == p[j]) j++;
if (j == n) cout << i - j + 1 << ' ';
} //输出出现位置的起始下标
(1)KMP字符串：
https://www.acwing.com/problem/content/833/
2.Trie：
(1)字符串统计：
https://www.acwing.com/problem/content/837/
(2)最大异或对：
https://www.acwing.com/problem/content/145/
3.并查集：
int p[N];
//查询+路径压缩
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
//合并
p[find(a)] = find(b);
[HTML_REMOVED]
3.1 并查集：
(1)合并集合：
https://www.acwing.com/problem/content/838/
(2)连通块中点的数量：
https://www.acwing.com/problem/content/839/
3.2 带权并查集：
(3)食物链：
https://www.acwing.com/problem/content/242/
4.栈：
4.1 栈：
(1)模拟栈：
https://www.acwing.com/problem/content/830/
(2)表达式求值：
https://www.acwing.com/problem/content/3305/
4.2 单调栈：
(1)单调栈：
https://www.acwing.com/problem/content/832/
5.队列：
5.1 队列：
(1)模拟队列：
https://www.acwing.com/problem/content/831/
5.2 单调队列：
(1)滑动窗口：
https://www.acwing.com/problem/content/156/
6.链表：
6.1 单向链表：
(1)单链表：
https://www.acwing.com/problem/content/828/
6.2 双向链表：
(1)双链表：
https://www.acwing.com/problem/content/829/
7.散列表：
(1)模拟散列表：
https://www.acwing.com/problem/content/842/
(2)字符串哈希：
https://www.acwing.com/problem/content/843/
8.堆：
(1)模拟堆：
https://www.acwing.com/problem/content/841/
(2)堆排序：
https://www.acwing.com/problem/content/840/
搜索：
1.DFS：
2.BFS：
数学：
1.数论：
1.1 质数：
1.1.1 试除法判质数：
bool is_prime(int x)
{
if (x < 2) return 0;
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0) return 0;
}
return 1;
}
(1)试除法判质数：
https://www.acwing.com/problem/content/868/
1.1.2 线性法筛质数：
int prime[N], cnt, st[N];
//得到1~n中的质数个数cnt
void get_prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] <= n / i; j++)
{
st[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
(1)线性法筛质数：
https://www.acwing.com/problem/content/870/
1.2 约数：
1.2.1 试除法求约数：
//输出x的约数
void get_div(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i++)
{
if (x % i == 0)
{
res.push_back(i);
if (x / i != i) res.push_back(x / i);
}
}
sort(res.begin(), res.end());
for (auto item : res)
{
cout << item << ' ';
}
}
(1)试除法求约数：
https://www.acwing.com/problem/content/871/
1.2.2 约数个数：
(1)约数个数：
https://www.acwing.com/problem/content/872/
1.2.3 最大公约数：
int gcd(int a, int b)
{
if (a % b == 0) return a;
return gcd(b, a % b);
}
(1)求最大公约数：
https://www.acwing.com/problem/content/874/
1.3 欧拉函数：
1.3.1 求欧拉函数：
int euler_phi(int n)
{
int ans = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
{
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
(1)求欧拉函数：
https://www.acwing.com/problem/content/875/
1.3.2 筛法求欧拉函数：
//求1~n中每个数的欧拉函数
int prime[N], idx, euler[N];
bool st[N];
void get_euler(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!st[i])
{
prime[idx++] = i;
euler[i] = i - 1;
}
for (int j = 0; prime[j] <= n / i; j++)
{
st[i * prime[j]] = 1;
if (i % prime[j] == 0)
{
euler[i * prime[j]] = euler[i] * prime[j];
break;
}
else
{
euler[i * prime[j]] = euler[i] * (prime[j] - 1);
}
}
}
}
(1)筛法求欧拉函数：
https://www.acwing.com/problem/content/876/
1.4 扩展欧几里得：
1.4.1 扩展欧几里得算法：
//a*x+b*y=gcd(a,b)
//求出xy同时返回gcd(a,b)
int exgcd(int a, int b, int& x, int& y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y = y - a / b * x;
return d;
}
(1)扩展欧几里得算法：
https://www.acwing.com/problem/content/879/
(2)线性同余方程：
https://www.acwing.com/problem/content/880/
1.5 中国剩余定理：
(1)表达整数的奇怪方式:
https://www.acwing.com/problem/content/206/
1.6 乘法逆元：
1.6.1 快速幂求乘法逆元：
binpow(a, p - 2)
(1)快速幂求乘法逆元：
https://www.acwing.com/problem/content/878/
1.7 线性同余方程：
1.7.1 扩展欧几里得求线性同余方程：
//a*x≡b(mod m)
int liEu(int a, int b, int m, int x, int y)
{
int d = exgcd(a, m, x, y);
if (b % d) return -1;
else return x * b / d % m;
}
(1)线性同余方程：
https://www.acwing.com/problem/content/880/
2.组合数学：
2.1 组合计数：
2.1.1 递推法求组合数：
特点：多次询问，数据较小
long long C[N][N];
const int mod;
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == 0) C[i][j] = 1;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
时间：O(N^2)
(1)递推法求组合数：
https://www.acwing.com/problem/content/887/
2.1.2 预处理的乘法逆元求组合数：
特点：多次询问，数据较大
long long fact[N], infact[N];
const int mod;
void init()
{
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i++)
{
fact[i] = fact[i - 1] * i % mod;
infact[i] = infact[i - 1] * binpow(i, mod - 2, mod) % mod;
}
}
long long C(long long a, long long b)
{
return fac[a] * infac[b] % mod * infac[a - b] % mod;
}
时间：O(NlogN)
(1)预处理的乘法逆元求组合数：
https://www.acwing.com/problem/content/888/
2.1.3 Lucas定理求组合数：
特点：询问次数少，数据非常大(a,b大于mod)
const long long mod;
long long C(long long a, long long b)
{
if (b > a) return 0;
long long res = 1;
for (int i = 1, j = a; i <= b; i++, j--)
{
res = res * j % mod;
res = res * binpow(j, mod - 2) % mod;
}
return res;
}
long long lucas(long long a, long long b)
{
if (a < mod && b < mod) return C(a, b);
return C(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}
时间：O(mod * logN * log mod)
(1)Lucas定理求组合数：
https://www.acwing.com/problem/content/889/
2.1.4 质因数分解的高精度乘法求组合数：
特点：不取模，结果非常大，需要使用高精度
int cnt[N], prime[N], idx;
bool st[N];
//筛选质因数
void get_prime(int x)
{
for (int i = 2; i <= x; i++)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] <= x / i; j++)
{
st[prime[j] * i] = true;
if (i % prime[j]) break;
}
}
}
//统计n!中质数p的个数
int get_cnt(int n, int p)
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
//计算组合数
void C(int a, int b)
{
vector<int> res;
res.push_back(1);
get_prime(a);
for (int i = 0; i < idx; i++)
{
int p = prime[j];
int cnt = get_cnt(a, p) - get_cnt(b, p) - get_cnt(a - b, p);
for (int j = 0; j < cnt; j++)
{
res = mul(res, p);
}
}
//输出res
for (int i = res.size() - 1; i >= 0; i--)
{
cout << res[i];
}
}
(1)质因数分解的高精度乘法求组合数：
https://www.acwing.com/problem/content/890/
2.2 Catalan数列：
[HTML_REMOVED]
(1)满足条件的01序列:
https://www.acwing.com/problem/content/891/
2.3 容斥原理：
[HTML_REMOVED]
(1)能被整除的数：
https://www.acwing.com/problem/content/892/
3.快速幂：
3.1 二进制取幂：
const int mod;
long long binpow(long long a, long long b)
{
long long res = 1;
while (b)
{
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
(1)二进制取幂：
https://www.acwing.com/problem/content/877/
4.线性代数：
4.1 高斯消元：
4.1.1 高斯消元解线性方程组：
(1)高斯消元解线性方程组：
https://www.acwing.com/problem/content/885/
4.1.2 高斯消元解异或线性方程组：
(1)高斯消元解异或线性方程组：
https://www.acwing.com/problem/content/886/
5.博弈论：
5.1 公平组合游戏：
有向图游戏和SG函数：
[HTML_REMOVED]
(1)Nim游戏：
https://www.acwing.com/problem/content/893/
(2)台阶-Nim游戏：
https://www.acwing.com/problem/content/894/
(3)集合-Nim游戏：
https://www.acwing.com/problem/content/895/
(4)拆分-Nim游戏：
https://www.acwing.com/problem/content/896/
DP：
狭义DP：优化问题 广义DP：优化问题+计数DP等非最优化问题
本质：将状态描述为顶点，状态转移描述为边，DP的过程就是对这个有向无环图不重不漏的进行遍历
关于状态：
状态(g[i][j])是一个子结构，是满足一个子问题条件的可能解(优化问题)或所有解(计数DP问题)的集合；
状态通常用状态信息(i和j)表示；
状态的最优解(优化问题)或大小(计数DP问题)即是f[i][j]
最优子结构性：利用子结构(g[i][j])中的最优解(f[i][j])可以推导出更大的子结构的最优解
思路：
状态表示：找维度，状态信息可以简化为几个维度；用一个集合g[i][j]上的的最优解f[i][j]表示状态
状态转移：用已知状态推导未知状态，可以对状态g[i][j]进行划分来便于表示
边界状态：初始化
求解顺序：依据状态转移方程
1.背包DP：
1.1 0-1背包：
状态表示：f[i][j]，在前i个物品中选，且总体积不大于j的最大价值
状态转移：如果v[i] <= j, f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])；反之，f[i][j] = f[i - 1][j]
滚动数组优化：
https://www.acwing.com/solution/content/177375/
(1)0-1背包问题：
https://www.acwing.com/problem/content/2/
1.2 完全背包：
状态表示：f[i][j]，在前i个物品中选，且总体积不大于j的最大价值
状态转移：f[i][j] = max(f[i][j - v[i]] + w[i], f[i - 1][j])
状态转移方程的优化：
https://www.acwing.com/solution/content/180720/
(1)完全背包问题：
https://www.acwing.com/problem/content/3/
1.3 多重背包：
1.3.1 二进制分组优化的多重背包：
状态表示：f[i][j]，在前i个物品中选，且总体积不大于j的最大价值
状态转移：如果v[i] <= j, f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])；反之，f[i][j] = f[i - 1][j]
二进制优化：s[i]=2^0+……+2^n+c；数0~s[i]可以由2^0、……、2^n、c组合而成;故可将第i件物品按每堆2^0、……、2^n、c个的分法分成n+1个物品
(1)多重背包问题—二进制优化版：
https://www.acwing.com/problem/content/5/
1.4 分组背包：
状态表示：f[i][j]，在前i组物品中选，且总体积不大于j的最大价值
状态转移：f[i][j] = max(f[i-1][j], f[i-1][j - v[i][1]] + w[i][k], f[i - 1][j - v[i][2]] + w[i][2],......, f[i - 1][j - v[i][s[i]]] + w[i][s[i]])，其中要求v[i][k] > j
(1)分组背包问题：
https://www.acwing.com/problem/content/9/
2.区间DP：
特点：(by：OI-WiKi)
特征：能将问题分解为能两两合并的形式；
求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值
思路：从区间大小为1开始，逐步迭代至整个题目所给区间，一般通过合并实现
(1)石子合并：
https://www.acwing.com/problem/content/284/
3.状态压缩DP：
特点：通过将状态信息压缩为整数，使得多个维度压缩为一个维度
(1)蒙德里安的梦想:
https://www.acwing.com/problem/content/293/
(2)最短Hamilton路径：
https://www.acwing.com/problem/content/93/
4.计数DP：
特点：一般要求一个集合S的大小，不能暴力枚举
思路：若将集合 S 分成若干无交的子集，那么 S 的元素个数就等于这些部分的元素个数的和；若子集的计数恰好与S的计数类似，则可以继续将子集划分……
(1)整数划分：
https://www.acwing.com/problem/content/description/902/
https://www.acwing.com/solution/content/2954/
5.数位DP：
特点：(by：OI-WiKi)
要求统计满足一定条件的数的数量(即，最终目的为计数)；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间(有时也只提供上界)来作为统计的限制；
上界很大(比如 10^18)，暴力枚举验证会超时
思路：(by：OI-WiKi)
考虑最朴素的计数方法，就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减
(1)计数问题：
https://www.acwing.com/problem/content/340/
6.记忆化搜索：
特点：通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历
(1)滑雪：
https://www.acwing.com/problem/content/903/
7.树形DP：
特点：初始状态数据结构为树的DP，一般递归解决
(1)没有上司的舞会：
https://www.acwing.com/problem/content/287/
8.基础DP：
8.1 最长公共子序列：
状态表示：f[i][j]，A长度为i的前缀子串和B长度为j的前缀子串的最长公共子序列
状态转移：如果a[i] == b[j]，则f[i][j] = f[i - 1][j - 1] + 1；否则，f[i][j] = max(f[i - 1][j], f[i][j - 1])
(1)最长公共子序列：
https://www.acwing.com/problem/content/description/899/
8.2 最长上升子序列：
思路：维护数组f，每处理一个数字，更新一次f；
f[i]表示当前已处理数字序列的长度为i的上升子序列中的最小结尾数字，明显f天然有序；
当处理完所有数字后，f大小即为LIS的大小；
对当前待处理数字a[i]，若a[i]大于f中的所有数，则push_back(a[i])；
否则，二分查找到第一个大于等于a[i]的数f[l],f[l]=a[i]；
时间：O(nlogn)
关于f[l]=a[i]：因为f[l]之前的数都小于a[i]，a[i]可以加在其对应的子序列之后，使子序列长度+1，于是长度为l-1的子序列们尾后加上a[i]，组成了长度为l且最小结尾数小于之前的f[l]的子序列，根据f定义，故更新f[l]为a[i]
(1)最长上升子序列：
https://www.acwing.com/problem/content/898/
8.3 数字三角形：
状态表示：f[i][j]，从(i,j)到最底层最大数字和
状态转移：f[i][j] = max(f[i + 1][j],f[i + 1][j + 1]) + a[i][j]
(1)数字三角形：
https://www.acwing.com/problem/content/900/
图论：
链式前向星：
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
1.最短路：
1.1 Dijkstra：
特点：单源最短路径，边权为正
思路：迭代n次，每次从未访问的点中选出到源点距离最小者，并对该点的所有出边进行松弛操作(更新邻点)
1.1.1 朴素Dijkstra：
特点：适合稠密图
时间：O(n^2)
(1)朴素Dijkstra1求最短路：
https://www.acwing.com/problem/content/851/
1.1.2 堆优化的Dijkstra：
特点：适合稀疏图
关于st数组：记录点是否已被选出(即是否已被更新为最短)，便于直接跳过堆中的冗余项。不同于朴素Dijkstra ，堆不支持更新元素。考虑一种情况，当已更新但非最短路的元素{d[x],x}在堆中，而在后面的遍历中x距离被再次更新，{d[x]’,x}入堆，此时堆中便同时存在一个点的两个元素(可以证明在x再次被更新前，{d[x],x}不会弹出)，而先入堆者距离一定更长，为冗余项，遇到了之后continue即可。相当于堆优化的Dijkstra用x的再次入堆等效了朴素Dijkstra的对x直接更新
时间：O(mlogm)
(1)堆优化的Dijkstra求最短路：
https://www.acwing.com/problem/content/852/
1.2 bellman-ford:
特点：单源最短路径，边权可为负
思路：本质是类似BFS的求最短路径，但是允许点的重复访问，因为点在第一次被访问时的路径可能不是最短
1.2.1 朴素bellman-ford:
特点：可处理负权回路，因为可以规定遍历次数，不会死循环
思路：规定遍历次数k，对所有边进行k次遍历并进行松弛操作
时间：O(nm)
(1)朴素bellman-ford求最短路:
https://www.acwing.com/problem/content/855/
1.2.2 队列优化的bellman-ford：
特点：不可处理负权回路
时间：一般O(m),最坏O(nm)
关于st数组：记录点是否在队列中，防止同一个点在同一个层次(相对于源点)多次入队，同时允许一个点通过多条不同长度的路径入队，来正确地更新其邻点
(1)队列优化的bellman-ford求最短路：
https://www.acwing.com/problem/content/853/
(2)队列优化的bellman-ford判负环：
https://www.acwing.com/problem/content/854/
1.3 Floyd：
特点：边权可为负，不可处理负权回路
思路：动态规划：
状态表示：d[k,i,j]，从i到j仅经过1~k点的路的最短距离
状态转移：d[k,i,j]=d[k-1,i,k]+d[k-1,k,j]
时间：O(n^3) 空间：O(n^2)
(1)Floyd求最短路：
https://www.acwing.com/problem/content/856/
2.最小生成树：
2.1 Prim：
思路：将点集分为两部分，已处理的点和未处理的点；
迭代n次，每次从未处理的点中选出一个到所有已处理点距离最近的点，加入到已处理点中，并用此点更新其邻点到已处理点的最短距离。
即已处理点和未处理点之间的最短桥构成最小生成树。与朴素Dijkstra唯一不同的是对点的更新方式
2.1.1 朴素Prim：
时间：O(n^2+m)
(1) 朴素Prim求最小生成树：
https://www.acwing.com/problem/content/860/
2.2 Kruskal：
思路：初始状态下，所有点的连通域仅有自己；
按权值大小对所有边进行升序排序；
对每条边，若两端点不连通，则用该边将两点连通；反之，继续处理下一边
时间：O(mlogm)
(1)Kruskal求最小生成树：
https://www.acwing.com/problem/content/861/
3.拓扑排序：
思路：记录每个点的入度，入度为零的点入队；
依次弹出入度为零的点，并删去该点的出边，即出边终点入度减1；
入度为零的点入队……
时间：O(m+n)
(1)有向图的拓扑序列:
https://www.acwing.com/problem/content/850/
4.二分图：
4.1 判二分图：
4.1.1 染色法判二分图：
思路：对任一未染色的顶点染色；
对于其相邻的顶点：
若未染色则将其染上和相邻顶点不同的颜色；
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，反之继续
(1)染色法判二分图：
https://www.acwing.com/problem/content/862/
4.2 二分图的最大匹配：
4.2.1 增广路算法：
思路： 对于每个左部点，我们都尽量为它匹配一个右部点；
对于某个等待匹配的左部点x，以及x的某个相邻的右部点y：
若y未被匹配，则xy相匹配；
若y已被匹配，则尝试让与y匹配的左部点x’再找一个右部点进行匹配，若x’重新匹配成功，则x与y匹配；若x‘匹配失败，则x尝试与它的下一个相邻右部点y’进行匹配……
若x与相邻右部点均匹配失败，则x无匹配右部点
时间：O(nm)
(1)增广路算法：
https://www.acwing.com/problem/content/863/
