「Note」广义串并联图

学学东西吧。

从平面图开始

定义

在一个平面图上，如果能够画出无向图 $G$ 的图解，并且其中没有任何边的交叉，则称其为平面图。注意到有些图表面看上去是有边的交叉，但是可以通过重画满足上面的约定，这也算是平面图。

判定 / Kuratowski

首先有观察法，显然只适合手玩，下面介绍一种叫 Kuratowski 的方法。
给出一些操作的定义。

• Kuratowski Graph： $K_{3, 3}$ 是点数最少的非平面图，$K_5$ 是边数最少的非平面图。
• 同胚操作： 在原图的边上增加或者删除度数为 $2$ 的点，不影响图的平面性。简单理解为，把一条边替换成一个连接该边两点的新节点，或者是其逆向操作。
• 同胚图： 设 $G_1, G_2$ 是两个无向图，$G_1, G_2$ 互为同胚图当且仅当可以通过同胚操作将 $G_1, G_2$ 变为同构的两个图。
• Kuratowski Theory： 一个图是平面图当且仅当不存在和 $K_{3, 3}, K_5$ 同胚的子图。

广义串并联图

定义

• $m \le 2n$，是平面图
• 不存在同胚于 $K_4$ 的子图

性质

通过若干次删 $1$ 度点，缩 $2$ 度点，叠合重边，最后一定会仅剩下一个点。

应用

显然，树和仙人掌都是广义串并联图，但是大多数问题不会给出这么舒服的形式。真正重要的是利用若干次删 $1$ 度点，缩 $2$ 度点，叠合重边这样的操作可以将图上问题的维护变得更简单，这样的方法是关键。
更具体的有，对于一张图 $m \le n + k$，其中 $m$ 是边数，$n$ 是点数，$k$ 是一个较小的数，并且满足 $k \le n$。那么就可以使用上述方法把这张图缩成一个点数 $\Theta(k)$ 图。因为使用上述操作时 $m - n$ 的大小是不增的，当操作结束时，不存在二度点和一度点，所有点度数大于等于 $3$，于是有 $2m \le 3n$，又有 $m \le n + k \Rightarrow n \le 2k, m \le 3k$。

题目

口胡题

给定 $n$ 个点 $m$ 条边的无向图定向后为 DAG 的方案数。
$n, m \le 1e5, m - n \le 10$。

待补。

JOI Open 2022 T3 「通学路 / School Road」

依次考虑所有部分分：

• $m \le 40, n \le 18$：爆搜
• $m - n \le 13$：于是开始缩，缩完之后 $m \le 42$ 可以直接爆搜。更具体的来说，保留 $1$ 和 $n$，一度点直接删，叠合重边的时候，如果两条边不一样，就令边权为 $-1$，如果 $1 \to n$ 的最短路上存在了 $-1$ 的边，那么就有解，删二度点时，如果连接的两边中有一条为 $-1$，那么边权就是 $-1$，否则就是两边加和。
• 图为点双：和正解其实做法一致，先把图剖成几个点双，判断是否有一个点双内满足就行了，