题解

思路

把每对夫妻看成一个顶点。若男方 $B_i$ 曾与女方 $G_j$ 交往，就连一条从 $i$ 指向 $j$ 的边。

第 $i$ 对婚姻不安全，当且仅当顶点 $i$ 位于一个有向环中。沿环依次让每位男方与下一对婚姻中的女方结合，就能在拆散婚姻 $i$ 后重新组成全部情侣；反过来，任何重新配对相对于原婚姻都会分解成若干交替环，因此涉及婚姻 $i$ 的重新配对必然给出经过 $i$ 的有向环。

所以只需判断每个顶点是否属于大小至少为二的强连通分量。

做法

用姓名到夫妻编号的映射把每条旧关系转换为有向边。运行强连通分量算法，记录每个顶点所属分量及每个分量的大小。

若顶点所在分量大小至少为二，输出 Unsafe；否则输出 Safe。

正确性证明

若顶点 $i$ 位于有向环 $i=p_1,p_2,\ldots,p_k,i$，则男方 $B_{p_t}$ 都曾与女方 $G_{p_{t+1}}$ 交往。让这些男方沿环与下一位女方重新结合，环外夫妻保持不变，就能在婚姻 $i$ 拆散后重新组成 $n$ 对情侣，因此婚姻 $i$ 不安全。

若婚姻 $i$ 不安全，比较重新配对与原婚姻。每个人在两种配对中度数都为一，两组边的对称差分解为交替环。包含婚姻 $i$ 的交替环对应夫妻顶点图中经过 $i$ 的有向环，所以 $i$ 与环上其他顶点互相可达，属于大小至少为二的强连通分量。

因此算法对每对婚姻的判断都正确。

复杂度

• 时间复杂度：$O(n+m)$。
• 空间复杂度：$O(n+m)$。