PKUWC D2T2 环图 证明

· · 算法·理论

原题链接

题面

给你一张有向图，无重边无自环，定义一张新图，新图中的一个点对应原图的一个简单环，两个点有连边当且仅当对应的两个简单环有公共边，求新图连通块数量。

解法

首先一个简单环的每一个点必定处于同一个强连通分量，也就是说对于每个强连通分量问题是独立的，可以先对原图缩点，然后每个强连通分量单独求答案，最后加起来。

大胆猜测对于每个强连通分量，新图的所有点连通，然而这是错的。考虑直接构造出两个三元简单环，只交于一个点，即输入：

5 6
1 2
2 3
3 1
1 4
4 5
5 1

显然答案为 2。

发现问题的主要原因是强连通分量内有“割点”。于是大胆猜测对于每个强连通分量，若将其每条有向边视作无向边时没有割点，则新图所有点连通。

如果这个结论正确，则只需要对每个强连通分量，将有向边改为无向边，跑一边点双，显然一个简单环内所有点处于同一个点双，因此每个点双可以独立开，不难说明一个点双在原图上仍然是一个强连通分量，所以答案为点双数量。

证明

下面只考虑一张强连通图，且将有向边视为无向边后不存在割点的情况。

因为简单环的数量很多，所以考虑把简单环转化到边上。

定义原图中的两条边相邻，当且仅当存在某个简单环同时经过这两条边。相邻具有传递关系。显然只要证明出所有边连通即可。

考虑原图中一个点的所有出边，若他们互相连通，则对于这个点的入边，显然存在某个环经过了他以及某条这个点的出边，因此这条入边也与所有出边连通。所以只需证明一个点的所有出边连通即可。

记这个点为 rt，考虑以 rt 为起点进行一次有向图 dfs，图中的边会被划分为树边，前向边，返祖边，横叉边。

接下来考虑树边。考虑两条树边 $rt\to a$，$rt\to b$，且存在某个从 $a$ 子树指向 $b$ 子树的横叉边 $c\to d$。 和上面类似的去构造两个环。任取一条从 $d$ 出发回到 $rt$ 的路径 $l$，注意 $l$ 不可能存在 $a$ 子树内的点，这一结论由有向图 dfs 的性质保证。在树中找出路径 $b\to d$，记 $l$ 上最后一个在 $b\to d$ 上的点为 $p$，则存在两个简单环：$rt\to a\to c\to d\xrightarrow lrt$，$rt\to b\to p\xrightarrow lrt$，他们同时经过了 $p\xrightarrow lrt$ 这条路径，因此 $rt\to a$ 和 $rt\to b$ 这两条边是相邻的。 所以对于两个存在横叉边的子树，对应的两条树边相邻。记全集 $U$ 为所有 $rt$ 出发的树边，若存在非全集的子集 $S$，满足 $S$ 与 $U\setminus S$ 之间没有横叉边，则 $rt$ 是割点，这与我们的假设不符，所以不存在这种情况。 因此可以说明任意两条树边是连通的。因此一个点的所有出边都是连通的。得证。