图论杂题选讲

例题

1. 删点

题面：给定一个DAG，请问图中有多少个点满足删掉这个点及与其相邻的所有边后使得s无法到达t？

分析：拓扑排序，然后dp。令f[u]表示从s到u的方法数，g[u]表示从u到t的方法数，如果f[u]*g[u]==f[t]，则u满足要求。

2. CF698B Fix a Tree

题面：给定 $n \ (n \le 2 \times 10^5)$ 个结点的父亲，问至少修改多少个结点的父亲（根结点的父亲为自己），能使整张图变成一棵树？要求输出最少的结点数和任意一个方案。

分析：求连通块个数

3. USACO 2012 Jan Bovine Alliance

题面：给出 $n$ 个点 $m$ 条边的图（不一定连通， $1 \le n,m \le 10^ 5$ ），先将点和边分组。每条边要和它的两个顶点之一分在一组，点不可以和多条边一组（但可以单独一组）。求分组方案数（答案对 $10^9+7$ 取模）。

分析：分类讨论

• 若 $m>n$ ，无解；
• 若 $m=n$ ，图必为环+外向树，解为2；
• 若 $m=n-1$，图退化为树，解为 $n$ 。

注：使用并查集维护连通块的边数和点数。

4. 链型网络

题面：给定一张 $n$ 个点简单无环图，进行 $m$ 次操作，每次操作可以加边，或询问图中有多少个点满足删去这个点及其相连的边，图中的所有连通块都为链。 $(1 \le n,m \le 10^5)$

分析：考虑链本身的性质，一个图的每个连通块为链，等价于每个点的度数小于2且无环。

首先考虑图中是否有度数大于等于3的点u，如果存在1个度数大于3的点，我们只能去掉u或在u的度数为3时去掉与u的三个相邻点的一个，其他的点都不可能成为答案。

在加边过程中第一次出现度数为3的结点的时候，对于可能成为答案的4个点，分别维护一个去掉该点后的图，然后分别判断：加边时每个点度数均小于2且无环（用并查集）

剩下的就是每个点的度数均小于等于2的情况，这样每个连通块只能是链或简单环。下面进行分类讨论。

• 原图为无环，则答案为结点数 $n$ ；
• 原图为恰有一个简单环，则答案为环的大小；
• 其他情况，答案为0。

这只需要维护一个记录集合大小的并查集即可。