图论
割点，割边
如果删去一点，整个图的连通块数量增加，即是割点。
只有环上的边不是割边。
tarjan
dfs 树上不存在横叉边，只有反祖边。
判断一点是否是割点
对于一点，判断它的子树中是否有能连接到该点上方的返祖边。
记录 \(low_y\) 代表子树中能回溯到的最小的 dfn 值。
判断：\(low_n>dfn_x\)
注意对于根节点，必须有超过一个儿子才为割点。
求割边
与割点同理。
\(low_y>dfn_x\)
其中，要判断 \((x,y)\) 是否是割边，\(x\) 是 \(y\) 的父亲。
显然，非树边一定不是割边。
重边情况
特殊处理一下即可。
点双，边双
边双：对于一个子图，没有任何割边。
显然，边双彼此之间以割边相连。
一个边双?
点双
任何一个点删去后都不影响连通性。
一个点可能分属多个点双。
SCC
环是什么？
若 \(x\) 可达 \(y\)，且 \(y\) 可达 \(x\)，则称其强联通。
强联通具有传递性
对 SCC 进行缩点后，会变成一个 DAG。
注意，在有向图的 dfs 中存在横叉边。
-
非树边：完全没有
-
返祖边：有用
-
横叉边：部分有用
用栈来维护 SCC。
如果存在返祖边，SCC会变大。
横叉边：假设 \(x\rightarrow y\) 是一条横叉边，若 \(y\) 在 LCA 的一个 SCC 里，就是有用的，此时等价于返祖边；否则没用。
类似割边。
把最浅的点视为代表点。
注意，此时 low 要维护在栈中的最小 dfn。
用 low 来实现隐式合并。
P3469
求每个点是不是割点后统计把 dfs 树分成了几部分，排列组合统计。
P1407
尝试给边加上方向，如果是夫妻关系：男 $\rightarrow $ 女，情人：女 \(\rightarrow\) 男。
看一下每对关系是不是在一个强联通分量。
UOJ67
考虑树是 \(n\) 个点，\(n-1\) 条边的连通图。
连通：不是割点
边数：自己判
P3225
sb计数题
缩点后会形成一棵树。在每一个叶子都建一个出口。
至于为什么会形成一棵树？
缩完以后如果不是树，则证明有环（无向图），于是可以再缩。
二分图
选出一些边，使得没有共同节点。
增广路/匈牙利算法
从一个匹配点出发，经过一条匹配边，再经过一条非匹配边，……，最后到达一个非匹配点。
如果存在这样的增广路，一定能使答案增大。
P2055
把床建在左部，人建在右部，按照能不能睡连边，进行最大匹配。
P4304
最小点覆盖
选择最少的点使得每条边都能选中。
做法看ppt。
最大独立集
最小点覆盖的补集。
对网格图进行二分图染色。
发现马攻击的位置一定与自己颜色不同。
把具有攻击关系的点连边，对二分图求最大独立集。
P1129
每一行建点，每一列建点，如果 \((x,y)\) 是黑色，则把 \(x\) 和 \(y\) 连边。
结论：如果有解，则是完美匹配。
不会证明。
网络流
源点 \(S\)，汇点 \(T\)。
\(\sum_{e\in in}=\sum_{e\in out}\)。
最大化 \(\sum_{e\in{S}}\)。
后面没听懂。
如果找不到增广路，就是最大流（？）
EK
Dinic
dinic:\(O(n^2m)\)，但复杂度玄学。
最大流最小割
二分图匹配转网络流
时间复杂度 \(O(m\sqrt{n})\)
圆桌问题
试题库问题
最小路径覆盖问题
拆点
最长不下降子序列问题
拆点
标签：day6,割点,SCC,割边,返祖,寒假,low,2.7,横叉边 From： https://www.cnblogs.com/BYR-KKK/p/18010881