图论 Part 2
wind_boy
·
2026-03-28 07:51:30
·
个人记录
耳分解
定义 ：对无向连通图 G ，若连通图序列 (G_0,G_1,\cdots,G_k) 满足：
则称 (G_0,G_1,\cdots,G_k) 是 G 的一个耳分解. 特别地，若 x_1\neq x_l 总是满足，则又称为开耳分解.
类似地，也可以得到有向图的耳分解.
定理 1 ：无向连通图 G 存在耳分解当且仅当 G 边双连通.
证明：
必要性显然，考虑充分性. 下面是构造：
任取一棵 dfs 树，初始 G_0 只含根.
考虑由 G_{i} 生成 G_{i+1} . 取树边 (x,y) 满足 x\not\in V_{i},y\in V_{i} ，由于 G 边双连通，故存在非树边 (u,v)\pod{u\not\in V_{i},v\in V_i} 覆盖 (x,y) ，将 v\sim u\sim y 作为耳加入.
不难发现此过程中 V_i 一定是包含根的连通块.
最后可能剩一些非树边，每条边单独作为耳加入即可.
根据 定理 1，我们用耳分解刻画边双.
具体来说，考虑通过状压 dp 实现加环的过程. 设 f_{S,x,y} 表示已经加入了点集 S ，当前的耳已经加到了点 x ，最终这个耳要接到 y 上，已确定边权和最小值. 转移枚举 x 下一个点.
复杂度 O(2^nn^3) .
证明和 定理 1 类似.
定理 4 ：无向连通图 G 是边双当且仅当可以将边定向使其强连通.
根据耳分解可直接证明（当然也可以不用耳分解）.
双极定向
定理 1 ：给定无向连通图 G 和两个不同节点 s,t ，以下四个条件等价.
连接 s,t 后 G 点双连通.
对 G 建圆方树后，所有方点都在路径 s\sim t 上.
存在一种定向为 DAG 的方法，使得有且仅有 s 入度为 0 ，有且仅有 t 出度为 0 .
初始所有点为白，依次将每个点染黑，要求 s 最先染黑，t 最后染黑，且任意时刻黑点连通、白点连通.
首先 1,2 显然等价. 3\to 4 只需取拓扑序，4\to 3 只需从拓扑序小的连向拓扑序大的.
考虑 4\to 1 的逆否命题. 如果连接 s,t 后存在割点 x ，那就意味着将 x 删掉后存在连通块 W 不包含 s,t ，而 x 又必须在 W 之前染黑，故不存在染黑方案.
考虑 1\to 3 .
连接 s,t 后取出 G 的耳分解，要求 (s,t)\in G_0 . 将 (s,t) 从 G_0 删去，并将剩余边从 s 到 t 定向得到 G' .
接着不断往 G’ 加耳 x_1\sim x_2\sim\cdots\sim x_k ，若 x_1 可以到达 x_k 则定向为 x_1\to x_2\to\cdots\to x_k ，否则反向. 不难发现该构造合法.
该做法源于以下两个性质：
取出以 s 为根的 dfs 树，若一个点有多个向上的返祖边，只需保留最浅的那个.
若一个点 x 度数为 2 ，那么一旦染黑了 x 的某个邻居，则立刻染黑 x 一定不劣. 于是可以据此进行“删二度点”的操作.
于是我们先不断根据 性质 1 删边，这样所有叶子的度数恰为 2 . 设某叶子 x 的两个邻居为 y,z ，则在新图 G' 中连 y\to x,z\to x ，然后在 G 中将 (y,x)(x,z) 替换为 (y,z) .
于是我们可以不断通过上述操作缩叶子. 最后在 G' 上搜一遍即可，需要按照加入时间从小到大枚举出边.
复杂度 O(n) .
模板：CF730K Roads Orientation Problem / CF1916F Group Division / code
建圆方树.
考虑确定 s,t 时怎么做. 可以发现一旦染黑了 x （x 与路径 s\sim t 的距离不超过 1 ），那么满足以下条件的 y 就都要同时被染黑：y 到路径 s\sim t 上的最后一个圆点为 x . 记满足条件的 y 的个数为 p_x ，那么 k_{\min} 恒等于 \max_x p_x .
考虑原问题. 从 l=\text{LCA}(s,t) 往下延伸，不难证明 l 一定往最重和次重的儿子延伸，接下来一定往最重的儿子延伸，因此容易 dp 求解.
例题 2 ：Qoj11115. Grotesque Team Reconstruction
建出圆方树，那么 S_1,S_2 一定形如：存在一个方点 x ，将 x 定为根，x 的任意子树要么完全属于 S_1 要么完全属于 S_2 .
枚举方点 x ，相当于 x 的每个邻居 y 有一个 0\sim 2 的权值，表示 y 子树圆点数模 3 . 我们需要将 x 代表的点双划分为两个集合 U,V ，使得每个集合的权值和模 3 都等于 2 .
如果存在一个权值为 2 的点，那么必然有解. 如果只有一个 1 ，其余为 0 ，则必无解.
否则，进行双极定向，那么必然存在一个前缀有恰好 2 个 1 ，有解.
例题 3 ：P5811 [IOI 2019] 景点划分
不妨设 a\leq b\leq c ，且 A,B 连通.
最多只有一个点双同时包含 A,B . 枚举该点双代表的方点 x .
若存在一个子树 >n-a ，那么必然无解.
若存在一个子树 \geq b ，那么 B 取该子树的点，A 取子树外的点即可.
否则，求出双极定向. 初始 A 为空，B 为全局，不断往 A 加点集 V ，一旦 |A|\geq a 就立刻结束. 由于 |V|<b ，故最终 a\leq|A|\leq a+b=n-c\leq n-b ，即 |B|\geq b .
在 A,B 中分别取出大小为 a,b 的连通块即可.
竞赛图
若无自环有向图 G 满足，任意两个点间恰有一条有向边，则 G 为竞赛图.
将竞赛图缩点后，不妨设其拓扑序为 1,2,\cdots,n' ，那么显然任意两点 i<j 间都存在 i\to j 的边.
[ARC163D] Sum of SCC
定理 1 （Redei 定理）：竞赛图存在哈密顿路径.
增量构造，假设 v_{1\sim k} 的哈密顿路径为 v_1\to v_2\to\cdots\to v_k ，考虑插入 v .
若 v\to v_1 存在或 v_k\to v 存在，则直接将 v 插入到开头或结尾即可.
否则意味着 v_1\to v\to v_k 存在，故必然存在 i 使得 v_i\to v\to v_{i+1} 存在，将 v 插入到 v_i,v_{i+1} 之间即可.
若使用二分寻找 i ，则除输入外复杂度 O(n\log n) .
CF1514E Baby Ehab's Hyper Apartment
定理 2 （Camion-Moon 定理）：强连通竞赛图存在哈密顿回路.
一个简单的想法是增量构造，维护环 v_1\to v_2\to\cdots\to v_k\to v_1 ，若 v_{1\sim k} 向 v 有连边，且 v 向 v_{1\sim k} 连边，那么就可以用类似求哈密顿路径的方法插入 v .
但是不一定存在这种好事，因此考虑做点操作创造这个条件.
求出原图的哈密顿路径，然后将所有点重标号，令 i\to i+1 有连边.
接着，找到最大的 k ，使得 k\to 1 有连边（也就是说 1 到 k+1\sim n 有连边），然后构造环 1\to 2\to \cdots\to k\to 1 .
由于原图强连通，故必存在未加入点 v 向 v_{1\sim k} 有连边，并且由于 1\to v 有连边，故可以将 v 插入.
复杂度 O(n^2) .
P3561 [POI 2017] Turysta
P4233 射命丸文的笔记
推论：若 G 为强连通竞赛图，则对任意 3\leq i\leq n ，存在长为 i 的环.
只需证明，n 个点的强连通图 G ，必存在一个 n-1 个点的强连通子图.
不妨设 1\to 2\to \cdots\to n\to 1 为 G 的哈密顿回路.
若存在 i 使得存在 i-1\to i+1 ，则 V\setminus\{i\} 强连通.
否则意味着对所有 i ，(i-1,i,i+1) 构成三元环，故将任意一点删去后剩下的图依然强连通.
定理 3 （Landau 定理）：设 p_{1\sim n} 不递减，则存在竞赛图，其出度序列为 p 的充要条件为：\forall 1\leq i\leq n:\sum_{j=1}^ip_j\geq \binom i2 ，且 \sum_{i=1}^n p_i=\binom n2 .
必要性：首先 \sum_{i=1}^n p_i 等于总边数 \binom n2 ，其次 \sum_{j=1}^ip_j 不小于 1\sim i 内的连边数 \binom i2 .
充分性：
初始令 G 所有边从右连向左，此时 p_i=i-1 ，考虑不断反转 G 中的边使得 p=p' .
相当于我们要选择若干互不相同的二元组 (u,v) ，满足 u<v ，然后将 p_u 加 1 ，p_v 减 1 .
反过来，变成对 p' 操作，要求最终 p'_i=i-1 .
考虑如下构造：
从小到大枚举 u ，从大到小枚举 v ，若 p'_u>u-1 且 \forall u\leq i<v:\sum_{j=1}^i(p_j'-j+1)>0 ，则将 p'_u 减 1 ，p'_v 加 1 .
考虑证明这个构造是对的.
首先不难发现每时每刻 p' 不递减，也就是说操作 (u,v) 的时候必满足 v=n 或 p'_v<p'_{v+1} .
接着，每时每刻必满足 p'_u-(u-1)\leq v-u ，这是因为若 p_u'-(u-1)=v-u ，则必然可以进行操作 (u,v) （这是因为 \forall u\leq j<v:p'_j\geq p'_u=v-1\geq j-1 ）. 故最终 p'_u 必然可以减到 u-1 .
CF850D Tournament Construction
推论：G 的强连通分量数为 \sum_{i=1}^n[\sum_{j=1}^ip_j=\binom i2] .
进一步地，设 0=b_0<b_1<\cdots<b_k=n 是所有满足 \sum_{j=1}^ip_j=\binom i2 的 i ，那么 (b_0,b_1],(b_1,b_2],\cdots,(b_{k-1},b_k] 构成强连通分量，并且靠后的强连通分量能到达靠前的.
CF1779E Anya's Simultaneous Exhibition
CF1498E Two Houses
Qoj5407. 基础图论练习题
gym103371K Three Competitions
定理 4 ：任取一个出度最大的点，这个点可以在两步之内到达其他所有点.
考虑反证. 设 x 出度最大，求出以 x 为起点的 bfs 树.
找到 bfs 树最深的点 y ，若 dis(x,y)\geq 3 ，那么意味着 y 可以一步到达 dis(x,z)\leq 1 的 z ，因此 d_y>d_x ，这与 x 出度最大矛盾.
该定理可以进一步扩展，见 Qoj9246. Dominating Point.
定理 5 ：三元环数等于 \dbinom n3-\sum_{i=1}^n\dbinom{d_i}2 .
考虑所有非三元环，他一定形如 a\to b,a\to c,b\to c ，因此取出存在 a\to b,a\to c 的所有三元组 (a,b,c) ，他们不重不漏地取遍了所有非三元环.
P10441 [JOIST 2024] 乒乓球 / Table Tennis
例题 1 ：给定一张竞赛图，对任意两个点 s,t 求出 s 到 t 的最小割. n\leq 5000 .
分析一下 S 到 T 的割：这等于起点在 S 的边数减去起终点都在 S 的边数，即 \sum_{x\in S}d_x-\binom{|S|}2 .
因此把 s,t 以外的点按 d 从小到大排序后，一定会选择一段前缀.
复杂度 O(n) .
由 定理 4 知，我们需要找到一个点，他能一步或两步到达其他所有点.
任取一个点 x ，记 x 能一步到达的点为 S ，一步能到达 x 的点为 T .
当 T=\varnothing 时 x 就是答案. 否则由于 T 可以两步到达 \{x\}\cup S ，故 T 内存在答案，递归下去即可.
由于所有点入度的平均值为 \frac{n-1}2 ，故每次随机一个 x ，问题规模期望减半，期望询问次数 O(n) .
例题 3 ：Qoj9246. Dominating Point
官解只能求 3 个，但其实可以求 k 个支配点.
首先根据 定理 4，第一个支配点可以取出度最大的点.
第二个点怎么取呢？一个想法是将第一个支配点删掉后取出度最大的点，但是这个点可能不能两步到达第一个支配点. 修正方法很简单：取能两步到达第一个支配点的点中度数最大的即可. 不断重复此过程.
同样考虑反证. 假设 x 能两步到达已确定的 k 个支配点且 x 度数最大，且 x 到 y 最短距离 >2 ，则可以证明 y 比 x 更优.
对所有 n 个点建出以 x 为起点的 bfs 树.
复杂度 O(kn^2) .
平面图
若可以将图 G 的顶点放到平面上，使得所有边（边可以是弯的）两两不交，则该图为可平面图.
定理 1（欧拉公式） ：若连通平面图有 v 个点，e 条边，f 个面，则 v-e+f=2 .
证明：首先图为树时成立，接着每加入一条边，e 加 1 ，f 加 1 ，故 v-e+f 不变.
扩展：当平面图不一定连通时，有 v-e+f=k+1 ，其中 k 为连通块数.
定理 2 ：若连通平面图有 v 个点，e 条边，则 e\leq 3v-6 .
由于任意一个面的边数 \geq 3 ，故 2e\geq 3f （2e 表示所有边的邻面数和，3f 表示所有面的邻边数和的最小值）.
故 2=v-e+f\leq v-e+\dfrac23e ，即 e\leq 3v-6 .
不难发现等号取到当且仅当每个面都是三角形.
定理 3 ：对于简单可平面图 G ，若在任意两个点加一条边后，得到的图都不是可平面图，则称 G 为极大可平面图.
一个图是极大可平面图，当且仅当每个面都是三角形. 此时 e=3v-6 .
定理 4（Fáry 定理） ：简单平面图总是存在一种平面嵌入，使得每条边都是直的.
定理 5（Kuratowski 定理） ：一个图是可平面图的充要条件为，其不含同胚于 K_5 或 K_{3,3} 的子图.
证明较长，且在 OI 中没啥用，从略.
P3249 [HNOI2016] 矿区
在求解平面图最小割的时候，我们经常将其转成对偶图的最短路.
P4001 [ICPC 2006 Beijing R] 狼抓兔子
例题 1 ：Qoj7756. Omniscia Spares None
特判 n\leq 6 .
根据 定理 3，我们只需考虑所有面为三角形的平面图即可，此时 m=3n-6 .
首先所有点度数 >1 ，其次若有点度数 =2 ，则该图为三角形，故所有点度数 \geq 3 ，因此该图一定有 n-4 个 6 度点和 4 个 3 度点.
增量构造.
点数足够了就把两端的五度点连起来.
这样可以构造出 n 为偶数的解.
可以证明 n 为奇数时无解.
例题 2 ：P7295 [USACO21JAN] Paint by Letters P
若两个同颜色点相邻，则连边.
现在问题变为，只保留给定矩形内的边，求连通块数.
根据 v-e+f=k+1 ，我们只需要计算出 v,e,f 即可.
我们求出原图的每个面. 若某个面不被给定矩形包含，则他和无穷远处相连，否则他不受到影响.
因此，一个简单的想法是，对每个面求出包含他的最小矩形，那么 $f$ 相当于给定矩形包含的矩形数，跑四维偏序即可.
考虑优化. 对每个面 $F_i$，我们任意选取面内的一个点 $P_i$，然后直接把给定矩形包含的 $P$ 的个数当做 $f$. 这样可能会算多，考虑修正. 可以发现 $F_i$ 被算多的必要条件是 $F_i$ 与给定矩形的边界有交，因此枚举给定矩形的边界，若边界上的面算多了就减回去即可.
复杂度 $O(nm+q(n+m))$.
- **例题 3**：[P8192 [USACO22FEB] Paint by Rectangles P](https://www.luogu.com.cn/problem/P8192)
考虑计算黑色区域数. 类似地，若两个黑点相邻，则连边，问题变为求连通块数.
根据 $v-e+f=k+1$，现在关键问题在于算 $f$.
考虑有哪些种类的面. 首先第一种是四元环，这是好统计的.
但是可能会出现黑矩形套白矩形的情况，导致面的种类比较复杂，怎么办.
但是可以发现，此时把矩形的边界提取出来后，这些线不是连通的. 换句话说，**如果所有矩形连通，则面只能是四元环**.
因此考虑把所有连通块找出来，分别计算贡献.
从左往右扫描线，扫到横线左端点就把它加到线段树内，扫到横线右端点就删掉，扫到一个竖线则将线段树 $[u,v]$ 内的所有横线与之相连.
具体来说，对线段树上每个节点 $[l_o,r_o]$，我们维护 $t_o$，若 $[l_o,r_o]$ 内没有横线则 $t_o=0$，若 $[l_o,r_o]$ 所有横线连通则 $t_o$ 为任意一个横线的编号，否则 $t_o=-1$. 若要将 $[l_o,r_o]$ 与 $x$ 相连，若 $t_o\neq -1$，那么就可以直接连接并退出了，否则递归到两个儿子连接，并将 $t_o$ 改为 $x$.
由于每额外往下递归一次就会有一个 $t_o$ 变成正数，总复杂度 $O(n\log n)$.
## 子图相关
- **三元环计数**
[P1989 【模板】无向图三元环计数](https://www.luogu.com.cn/problem/P1989)
将所有点按照 $deg_i$ 从小到大排序. 不妨设 $deg_i\leq deg_{i+1}$.
将所有边定向，从 $deg$ 较小的指向较大的.
设 $d_i$ 为将边定向后 $i$ 的出度.
由于 $deg_i\geq \sqrt {2m}$ 的点数不超过 $\sqrt{2m}$，故当 $i\leq n-\sqrt{2m}$ 时，$d_i\leq deg_i\leq \sqrt{2m}$；当 $i>n-\sqrt{2m}$ 时，$d_i\leq n-i\leq\sqrt{2m}$.
因此 $d_i\leq O(\sqrt m)$.
由于新图是 DAG，故所有三元环均形如 $a\to b,b\to c,a\to c$.
枚举边 $(a,b)$，枚举 $b$ 的出点 $c$，复杂度 $O(m\sqrt m)$.
- **四元环计数**
同样将所有边重定向.
由于新图是 DAG，故所有四元环均形如 $a\to b,a\to c,b\to d,c\to d$.
相当于对于所有 $(a,d)$，设 $s_{a,d}$ 为 $a\to c\to d$ 的 $c$ 的数量，需要将答案加上 $\dbinom{s_{a,d}}2$.
枚举 $a$，枚举 $a$ 的出点 $b$，枚举 $b$ 的出点 $d$，这样就可以求出所有 $s_{a,d}$. 然后找到 $s_{a,d}$ 不为 $0$ 的 $d$ 统计答案即可.
复杂度 $O(m\sqrt m)$.
- **例题 1**：[Qoj6354. K4](https://qoj.ac/contest/1212/problem/6354)
和四元环计数一样，先将所有边定向.
枚举编号最小的点 $a$. 建一张新无向图，若原图中边 $a\to b,a\to c,b\to c$ 均存在，则在新图中连无向边 $(b,c)$. 那么原图中 $(a,b,c,d)$ 形成 K4 当且仅当新图中 $(b,c,d)$ 形成三元环.
使用 bitset $O(\dfrac {n_am_a}{\omega})$ 计算三元环. 这里 $n_a=d_a\leq O(\sqrt m),\sum m_a=O(m\sqrt m)$，故复杂度 $O(\sum\dfrac{n_am_a}{\omega})=O(\sqrt m\sum\dfrac{m_a}{\omega})=O(\dfrac{m^2}{\omega})$.
- **例题 2**：[Qoj1836. Glory Graph](https://qoj.ac/problem/1836)
本质不同的子图只有以上 $6$ 种，设这六种的个数为 $x_1,x_2,x_3,x_4,x_5,x_6$.
考虑找到尽可能多的关于 $x$ 的等式，然后用这些等式线性组合出 $x_6-x_2$.
- 子图数 $\dbinom n4=x_1+x_2+x_3+x_4+x_5+x_6
满足边 AB,BC 颜色不同的有序四元组 (A,B,C,D) 个数：0\cdot x_1+8\cdot x_2+12\cdot x_3+12\cdot x_4+16\cdot x_5+16\cdot x_6 . 设 b_i,y_i 为与 i 相邻的蓝/黄边个数，则答案为 (n-3)\sum2b_iy_i ，这个容易 O(n^2) 求出.
满足边 AB,BC,CD,DA,AC 颜色相同的有序四元组 (A,B,C,D) 个数：24\cdot x_1+4\cdot x_2 . 这个可以枚举 A,C ，然后使用 bitset 计算.
满足边 AB,BC,CD,DA 颜色相同，AC 颜色不同的有序四元组 (A,B,C,D) 个数：4\cdot x_2+8\cdot x_5 ，这个也可以 bitset 计算.
于是
\begin{aligned}x_6-x_2=&-3(x_1+x_2+x_3+x_4+x_5+x_6)\\&+(2x_2+3x_3+3x_4+4x_5+4x_6)\\&+\dfrac12(6x_1+x_2)\\&-\dfrac12(x_2+2x_5)\end{aligned}
时间复杂度 O(\dfrac{n^3}{\omega}) .
定理 1 ：有 n 个顶点且不含三元环的图 G 的最大边数为 \lfloor\dfrac{n^2}4\rfloor .
考虑构造，从直觉上来看我们应该构造一个完全二分图.
具体地，当 n=2v 时，构造 K_{v,v} ；当 n=2v+1 时，构造 K_{v,v+1} .
下面证明他是最优的.
不妨设 1 的度数最大，为 d=d_1 ，不妨设 1 与 n-d+1\sim n 相连.
由于 n-d+1\sim n 两两没有连边，故总边数 \leq\sum_{i=1}^{n-d}d_i\leq d(n-d)\leq\lfloor\dfrac{n^2}4\rfloor .
定理 2 ：设图 G 有 n 个点 m 条边，那么 G 至少包含 \dfrac m3(\dfrac{4m}n-n) 个三元环.
假设 (u,v)\in E ，那么 u,v 的公共邻居至少有 d_u+d_v-n 个，也就是最少有 d_u+d_v-n 个三元环包含 (u,v) .
因此三元环数 \geq\dfrac13\sum_{(u,v)\in E}(d_u+d_v-n)=\dfrac13(\sum_{i=1}^nd_i^2-mn) .
由 \sum_{i=1}^nd_i=2m ，根据柯西不等式得 \geq\dfrac13(\dfrac1n(\sum_{i=1}^nd_i)^2-mn)=\dfrac13(\dfrac{4m^2}n-mn) .
当然，由于 d 必须是整数，所以等号通常是取不到的.
定理 3（托兰定理） ：
定义 T_k(n) 为：设 n=ks+r\pod{0\leq r<k} ，设 n_{1\sim r}=s+1,n_{r+1\sim k}=s ，则 T_k(n)=K_{n_1,n_2,\cdots,n_k} .
记 e_k(n) 为 T_k(n) 的边数.
那么若 n 个点的图 G 不含 K_{k+1} ，则边数 m\leq e_k(n) ，当且仅当 G 与 T_k(n) 同构时等号成立.
考虑仿照 定理 1 证明.
归纳，首先 k=2 时成立，考虑由 k-1 成立推出 k 成立.
不妨设度数最大的点为 1 ，设 1 与 n-d_1+1\sim n 相连，由于 G 不含 K_{k+1} ，故 n-d_1+1\sim n 不含 K_k .
因此 n-d_1+1\sim n 的连边数不超过 e_{k-1}(d_1) ，故总连边数不超过 (n-d_1)d_1+e_{k-1}(d_1)\leq e_k(n) .
定理 4 ：设 G 不含四元环，则 m\leq\dfrac14n(1+\sqrt{4n-3}) .
设 P_i 为 i 的邻居，那么 \forall u\neq v ，有 |P_u\cap P_v|\leq 1 .
因此 \sum_{i=1}^n\binom{d_i}2\leq\binom n2 ，即 \sum_{i=1}^nd_i^2-2m\leq n(n-1) .
根据柯西不等式，n(n-1)\geq\sum_{i=1}^nd_i^2-2m\geq\dfrac1n(\sum_{i=1}^nd_i)^2-2m=\dfrac{4m^2}n-2m .
解得 m\leq\dfrac14n(1+\sqrt{4n-3}) .
定理 5 ：若大小为 n=q^2+q+1\pod{q\geq 2} 的图不含四元环，则 m\leq \dfrac12q(q+1)^2 .
Qoj9699. Loving You in My Humble Way 这题给出了 q 为质数时 m 取到上界的一种构造.
考虑一个简单的问题：将 K_6 每条边染为黑白两色之一，证明一定存在同色三元环.
考虑 1 的邻边，一定存在三条边同色，设 (1,a)(1,b)(1,c) 均为黑色. 若 (a,b)(a,c)(b,c) 中存在一条边为黑，则意味着他与 1 构成三元环，否则 (a,b)(a,c)(b,c) 均为白，构成三元环.
考虑拓展. 记 r(c_1,c_2,\cdots,c_k) 为满足以下条件的最小的 n ：不存在将 K_n 染为 k 种颜色的方法，使得对每种颜色 i ，不存在颜色全为 i 的 K_{c_i} 子图.
那么可以证明 r 是有限的，并且 r(c_1,c_2,\cdots,c_k)\leq r(c_1-1,c_2,\cdots,c_k)+r(c_1,c_2-1,\cdots,c_k)+\cdots+r(c_1,c_2,\cdots,c_k-1)-k+2 .
同样考虑归纳. 记不等式右侧为 s . 考虑 1 的 s-1 条出边，根据抽屉原理，必然存在 i 使得颜色为 i 的出边数 \geq r(c_1,\cdots,c_i-1,\cdots,c_k) . 设颜色为 i 的出边的另一端的集合为 S ，那么若 \{v_1,v_2,\cdots,v_{c_i-1}\}\in S 的导出子图颜色全为 i ，则 \{v_1,v_2,\cdots,v_{c_i-1},1\} 的导出子图颜色全为 i . 因此根据归纳假设，必然存在 j 使得存在 K_{c_j} 颜色全为 j .
当然这只能求出 r 的上界，确切值还有待研究.
图论建模
若 (x,y) 的权值为 c ，则在二分图中连 x_l\sim y_r ，权值为 c . 那么我们要求的实际上就是大小为 k 的匹配的权值最大值.
跑原始对偶算法即可. 复杂度 O(k(n+m)\log(n+m)) .
首先操作次数显然是 n+m-1 .
考虑如何判断一个操作集合是否合法. 首先同一行同一列不能染多次. 其次若操作 A 必须在操作 B 之前，则连 A\to B ，则不能形成环.
因此对于一个操作 (x,y,c) ，若 c=\texttt R ，则连 x_l\to y_r ，否则连 x_l\leftarrow y_r ，则最终形成的有向二分图不能有环，且所有点出度不超过 1 .
因此，这个有向二分图实际上是一棵内向树. 因此我们只需计算 K_{n,m} 的生成树个数，最后乘根的位置数 n+m 即可.
考虑计算 K_{n,m} 的生成树个数. 考虑矩阵树定理的过程.
设 f_{n,k} 表示 K_{n,n} 的生成子图中有多少满足，恰好存在 k 个环，且每个点恰好在一个环内.
设 g_n=\sum_{k\geq 0}f_{n,k}(-1)^k ，那么答案为 \sum_{i\geq 0}\binom{n-1}i\binom mig_im^{n-1-i}n^{m-i} .
直接实现就是 O(n^3) . 但其实当 i\geq 2 时有 g_i=0 ，这是因为对于一个由若干偶环构成的二分图，交换 1_l,2_l 的出边后环数奇偶性改变，因此贡献抵消. 因此答案化简后为 m^{n-1}n^{m-1} .
复杂度 O(n^2) .
考虑如何判断是否有唯一解. 若 (i,j) 有棋子，则连 i_l\sim j_r ，最后会形成一个二分图. 那么问题就变成了给有公共点的边匹配.
显然每个连通块的边数必然为偶数. 若一个连通块是树，那么可以自底向上地匹配，这样至少可以得到一个解. 若一个连通块有环，那么对于环上的某一条边，其可以选择挂在任意一个端点上，这样可以得到至少两个方案. 因此有唯一解的必要条件是连通块为树.
那么什么样的树有唯一解呢？对于一个点 i ，设 d_i 为 i 的邻居中有多少个子树大小为奇数，那么有唯一解当且仅当 d_i 不超过 2 .
这个充要有一个等价的形式：任取一种匹配，对于每对匹配边 (a,b)(b,c) ，让 d_b 加 1 ，最后 d_i 均不超过 1 .
现在我们需要在连通块间连边，使得没有环且只能在左右部点间连边，且 d 均不超过 1 . 一个简单但重要的观察是，对于新加的一条边，找到与之匹配的边所在的连通块，那么另一个连通块是什么其实不重要，只需要保证没有连成环就可以了. 若新加的某条边与某个连通块内的边匹配，则称该边挂在了这个连通块上.
设左部点挂了 L 条边，右部点挂了 R 条边，左部点的孤点数为 s_l ，右部点的孤点数为 s_r ，点数大于 1 的连通块数为 s ，那么存在不成环的连边方案当且仅当 \max(L-s_r,0)+\max(R-s_l,0)<s .
对于每个连通块，我们容易 dp 出当左部点挂了 i 条边时，右部点至少要挂多少条边. 最后容易背包出合法的 (L,R) 对.
复杂度 O(n^2) .
例题 4 ：称一个序列是好的当且仅当他是由 [1,n]\cap\Z 构成的长为 n 的序列，且每种数出现次数不超过 k .
称两个序列是等价的当且仅当可以通过以下操作将一个序列变为另一个：
选择 1\leq x<y\leq n ，交换 a_x,a_y ，接着同时进行：将 a 中值为 x 的数变为 y ，将值为 y 的数变为 x .
问所有好的序列构成多少等价类.
连 x\to a_x ，会形成内向基环树森林. 而题述操作其实等价于交换 x,y 的出点和入点.
因此问题等价于求无标号基环树森林数，要求入度不超过 k .
先求出无标号基环树数，然后通过简单 dp 求出原问题答案.
首先使用简单 dp 计算出无标号有根树个数，然后通过 polya 定理将根串成环.
复杂度 O(n^3\log n) .
例题 5 ：Qoj9771. Guessing Game
建二分图，连 {a_k}_l\sim {b_k}_r ，i_l 表示 Alice 分配到 i ，i_r 表示 Bob 分配到 i .
接下来，第一轮，若 Alice 为左部点的叶子，那么 Alice 赢得游戏，把左部点的叶子删掉. 依次类推.
答案就是左右部点分别有多少被删了.
单独考虑二分图每个连通块.
假设该连通块是树，那么最后留下来的点一定是直径中点.
假设该连通块有环，那么环内的点和环之间的点是不可删点，把这些点之间的边删掉，将这些点作为根，就可以得到有根树森林.
建一个虚点，所有有根树的根连向这个点.
用并查集维护连通块. 对于有根树，维护每个点的父亲.
设新增的边为 (x,y) .
若 x,y 在同一无根树：爆搜重构整棵树即可.
若 x,y 在不同无根树：使用经典结论快速维护直径. 需要先建好最小生成树以便查询距离.
若 x 在有根树，y 在无根树：爆搜重构 y 所在的树.
若 x,y 在有根树：将 x,y 到根路径上的点的父亲都改为虚点.
复杂度瓶颈在于求距离，可以做到 O(n) .
例题 6 ：CF1270G Subset with Zero Sum
对式子变形得到 1\leq i-a_i\leq n .
连 i\to i-a_i ，边权为 a_i ，那么一条路径的权值和实际上就是位移.
因此，一个环的权值和就是 0 .
而我们连完 i\to i-a_i 后会得到一个基环树，因此必然存在一个环.
复杂度 O(n) .