P9013 题解

Demeanor_Roy · 2023-02-04 16:27:40 · 题解

• 摘自 here。

考虑将每个字母看作一个点，且将所有的 s_i 向 t_i 连边，同时去掉重边与自环，这样就构成了一张优美的图。

首先不难发现，如果某个点出度大于等于二，则一定无解。因为你没有办法把一个字母变成许多个不同的字母。

考虑图没有环的情况，发现按照拓扑序逆序变换即可，答案为边的数量。

有环呢？由于直接将环上点变换会导致无解，此时就必须借助环外点。接下来考虑环外点类型对答案的影响：

• 若借助某点 u，满足 u 向环上某点有连边。不难发现从此处破环即可。答案不变。

• 若借助字符串中不存在的点或者已经变换完成的联通块中入度为 0 的点，答案增加 1。

• 若不存在上述点，则无法破环，无解。

于是按照以上思路分讨即可。代码