算法
最小生成树 MST
最小生成树，即边权和最小的生成树。
Prim
时间紧迫，先不学了。
Kruskal
为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 条边，即形成了一棵树。
void kruskal(){ sort(e + 1, e + m + 1, cmp); //按边权排序 for(int i = 1; i <= m; i++){ int u = f(e[i].u), v = f(e[i].v); if(u == v) continue; //如果连通则不对最小生成树产生贡献，忽略 ans += e[i].w; unity(u, v); //并入同一集合 cnt++; if(cnt == n - 1) break; }}例一 HDU7226
边的上界小于 。
建图，最小生成树。
边权值域小，可以使用桶排去掉 。复杂度 。
例二 P2245 星际导航
找一条路径上边权的最大值。
-
用 Kruskal 建最小生成树。对于每个询问跑 LCA 。
-
Kruskal 重构树 可以维护最小生成树上最大边权的问题。
首先将所有边按边权从大到小排序。
从最小边开始。如果这条边的两个邻接点在同一个集合中，跳过；否则，建立一个虚点作为这两个点共同的祖先，让这个虚点的点权等于这条边的边权。
如此操作 次，就可以得到一个恰好有 个叶子的二叉树，每个非叶子节点刚好有两个儿子。这棵树就是 Kruskal 重构树。
例三 P2619 [国家集训队] Tree I
一种假解法：朴素贪心。对全部边进行排序，有白选白，直接选择 条白边。这样选择的话，生成树权值不为最小，会漏选更小权值的黑边。
正解：带权二分。
例四 P4180 [BJWC2010] 严格次小生成树
用 LCA 维护最小值和次大值。
例五 POJ2728 Desert King
最优比率生成树。
给定 个点的一个无向图，图中每对顶点间的边 有一个收益 和一个成本 。求该图的一个生成树 。。
0-1分数规划问题。分数规划 - OI Wiki
可以用二分答案解决。
连通性问题 Tarjan算法
例一 P1656 炸铁路
struct ANS{ int a, b;} ans[N];int anscnt;int dfn[N], low[N], dfsclock;void tarjan(int x, int diff){ low[x] = dfn[x] = ++dfsclock; for(int i = head[x]; i; i = edge[i].next){ if(i == (diff ^ 1)) continue; int y = edge[i].to; if(!dfn[y]){ tarjan(y, i); low[x] = min(low[x], low[y]); if(low[y] > dfn[x]){ ans[++anscnt].a = x; ans[anscnt].b = y; } } else low[x] = min(low[x], dfn[y]); //这里的 dfn[y] 可以换成 low[y] }}例二 P2227 [HNOI2001] 洗牌机
并查集
例题 P1536 村村通
并查集是一种树型数据结构，用来处理一些不相交集合的合并和查询问题。可以用来判断一个森林里有几棵树、某个节点是否属于某个数，等等。
代码实现：
int fa[N], n, m, x, y;//find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。int find(int x){ if(x != fa[x]) fa[x] = find(fa[x]); // 路径压缩，使祖先下的子节点尽可能多，优化find速度 return fa[x]; //返回祖先}//unity:将两个子集合并成一个集合。void unity(int x, int y){ int r1 = find(x); int r2 = find(y); fa[r1] = r2; //合并祖先}int main(){ cin >> n; cin >> m; for(int i = 1; i <= n; i++) //init fa[i] = i; for(int i = 1; i <= m; i++){ cin >> x >> y; unity(x, y); } return 0;}另一种 find() 的写法：
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]);}模拟赛 图论专项（二）
T1 P7991 [USACO21DEC] Connecting Two Barns S
用并查集维护不加边时会有几个连通块、每个点在哪一个连通块。用 来表示 所在的连通块的代表点。代表点即为这个连通块在并查集中的祖先。
如果只有一个连通块，那么ans = 0；如果有两个连通块，那么ans = 1；
如果有大于两个连通块，那么题目将被转化为，通过除了 和 的某一个连通块来连接。对于每一个连通块 ，计算其最小代价，维护 ans。
可以用二分答案优化。对于每一个点 ，upper_bound 查找 与 中离点 最近的点，然后分别遍历连通块中的点，维护最小值。
T2 P8191 [USACO22FEB] Moo Network G
观察到 ，暴力建边 + Kruskal。
T3 P7528 [USACO21OPEN] Portals G
T4 P8328 [COCI2021-2022#5] Usmjeravanje
参考
[图论 —— 生成树 - Alex_McAvoy](https://blog.csdn.net/u011815404/article/details/88625346)
P7991 [USACO21DEC] Connecting Two Barns S题解 - 洛谷专栏 (luogu.com.cn)