广义串并联图方法学习笔记

广义串并联图指不存在同胚于 $K_4$ 的子图的图，其中，我们称两个图同胚当且仅当这两个图可由同一个图通过边细分变换得到，边细分指删去一条边，新建一个点，并将新点与原边的两个端点连边。

广义串并联图是平面图，在删除重边后满足 $m\le 2n$。

任何广义串并联图可以通过删一度电，缩两度点，叠合重边的方法将原图变为一个单点，我们称这三种操作为广义串并联图方法。

值得一提的是，广义串并联图应该不是什么正式的学术名词，其起源于 2019 国家集训队论文《〈公园〉命题报告》，文中有关于上述性质的严格证明。

平时见到的树、仙人掌等都是广义串并联图。

虽然广义串并联图的概念并不常见，但广义串并联图方法很有启发性，2022 年连续出了 3 道这样的题目，参见 2023 冬令营张隽恺的题目选讲。

一般的说，在 $m-n$ 很小的时候都可以考虑使用广义串并联图方法。

在实现广义串并联图方法时我个人通常考虑使用队列维护待处理的点，用 map 存邻接矩阵，值表示边的编号。

例题：

仙人掌加一条边也是广义串并联图，维护每条边连接和断开的方案数，使用广义串并联图方法转移即可。

类似于广义串并联图方法，没有出度的点可以删掉，出度为一的点可以合并，每次询问，如果两个点中有任何一个被删去或两个点重合，则 Brain 胜利，否则 Hoof 胜利。

在实现时，我们维护一个点的所有入边，在合并出度为一的点是对入边做启发式合并，维护每个点的出度，用并查集维护点的合并和删除情况，当合并出度为一的点时，我们需要找出该点唯一可以到达的点，遍历该点初始时所有可以到达的点，找到其中未被删去的点即可。