8819

不可以，总司令。 [题目传送门](https://www.luogu.com.cn/problem/P8819) # 思路 首先，当图中每个点出度为 $1$ 时，从任一点出发必定会进入环。 证明：假设有一点不符合，则沿着它的出边一直走会到一个出度为 $0$ 的「终点」，与每个点出度为 $1$ 矛盾。 ......

生日，感慨万千。 我们废话不多说看题，这道题让我们对于一张图维护四个操作 1. 删一条边。 2. 删一点的所有入边。 3. 加入一条被删除的边。 4. 加入原图中一个点的所有入边。 每次都要问你一下这个图是不是所有点的出度都是 1。 动态维护一张图是肯定不可能的，可以肯定地说，所有让你动态维护图的题 ......

赛时因为 T4 这题一眼没看，事后发现真的神仙。 简化题面后条件为： 1. 所有点出度为 $1$。 2. 从所有点走出去都能走到环上。 不难发现条件仅为判断所有点出度为 $1$，即判断是否是一个**内向基环树森林**。 再看操作： 1. 删掉一条边 $(u,v)$ 2. 对于 $u$，将所有边 $( ......

图论 + 哈希。 [Link.](https://www.luogu.com.cn/problem/P8819) 因为实在是太妙了所以写个题解。 ## Solution - 因为每个点的出度都为 $1$，所以从任意一点出发永远可以走下去，故每次只需判断每个点度数是否为 $1$ 即可。 - 然后一三操 ......