目录
题目解析
画画图,就能想出来是 找环
直觉: 先想一种最简单的情况, 破坏 g1 -b1,怎么能最简单的配对呢
g1 - b1 -> g2 - b2 - g1
破坏 g1 - b1:
b1 -> g2
b2 -> g1
其他的n-2对, 还是原来的,不用动
可以将这个思维过程提炼为 “萝卜蹲”式的填坑逻辑：
- 起因（挖坑）： 一旦拆散夫妻 ，就会在原来的位置留下一个空缺，同时产生一个多余的人。
- 经过（挤位）： 这个多余的人去抢了夫妻 的位置，导致夫妻 的原配被挤出，又产生了一个新的多余人。
- 结果（回填）： 为了保证最后所有人都有位置（完美匹配），这串连锁反应中最后一个被挤出的人，必须恰好回到最初的那个空缺里去。
- 结论（成环）： 既然这一连串的“抢位”操作必须首尾相接才能完美收场，那他在几何结构上必然就是一个封闭的环。
1. 纯二分图匹配思路：“暴力拆婚”
如果你不想用 SCC（强连通分量），你想用纯粹的“二分图匹配”或“网络流”思路来做，本质上是在通过寻找增广路来验证边是否必须。
我们可以称这种方法为**“暴力拆婚验证法”**。
核心逻辑
我们已经知道
在二分图匹配（或最大流）的术语中，这意味着：
如果我们强制断开
如果能找到
具体算法步骤
对于每一对夫妻
- 暂时断开：在图中暂时忽略婚姻边
。 - 寻找路径：以
为起点，尝试用 DFS 或 BFS 寻找一条到达 的路径。注意，路径行走的规则必须符合交替路原则： - 必须走“旧情边”（没被匹配的边）从
到 （或者 到 ，取决于你如何定义左右部和边方向）。 - 必须走“婚姻边”（已被匹配的边）跳转。
- 必须走“旧情边”（没被匹配的边）从
- 判断：
- 如果能找到路径：说明存在交替环
Unsafe。 - 如果找不到路径：说明这条边是割边（桥），不可替代
Safe。
- 如果能找到路径：说明存在交替环
- 恢复：恢复边
，继续判断下一对。
2. 为什么通常不推荐这么做？（复杂度分析）
这就回到了这道题的数据范围问题。
- SCC 方法（Tarjan）：
- 只需要对全图遍历一次。
- 时间复杂度：
。 - 计算量：
约 次操作。秒杀。
- 暴力二分图匹配方法：
- 你需要对每一对夫妻（
对）都跑一次 DFS/BFS 找路径。 - 单次寻找路径的最坏复杂度是
。 - 总时间复杂度：
。 - 计算量：
次操作。
- 你需要对每一对夫妻（
结论
- 如果测试数据比较弱（图很稀疏，路径很短），这种
的做法可能会卡过。 - 如果测试数据构造了很长的链或复杂的环，这种做法必定 TLE。
这道题作为“国家集训队”的题目，考察点正是**“如何从
3. 代码演示（非 SCC 版本）
如果你想头铁试一下暴力 DFS，代码逻辑大概是这样的（仅供理解逻辑，大概率过不了全部测试点）：
C++
// 伪代码/核心逻辑片段
// 这种写法对应的是 O(N*(N+M))
vector<int> adj[MAXN]; // 邻接表只存旧情边 G -> B (或者 B -> G)
int match[MAXN]; // 记录当前的匹配对象
bool vis[MAXN]; // DFS 判重
// 试图寻找从 u 出发能不能绕一圈回到 target
bool findPath(int u, int target) {
for (int v : adj[u]) { // u 喜欢 v (旧情)
if (v == target) return true; // 找到了直接连回老公的边，形成环
// 这里的逻辑稍微需要转换一下：
// 标准匈牙利是找增广路，这里是在这就有的匹配图上找环
// 如果 v 已经结婚了（肯定结了），我们需要沿着 v 的婚姻边跳到 v 的老公 next_u
// 然后从 next_u 继续找
int next_u = match[v];
if (!vis[next_u]) {
vis[next_u] = true;
if (findPath(next_u, target)) return true;
}
}
return false;
}
// 主循环
for (int i = 1; i <= n; i++) {
// 设 boy[i] 和 girl[i] 是原配
// 我们想看能不能从 girl[i] 出发，走旧情边，最终绕回 boy[i]
memset(vis, 0, sizeof(vis));
// 从 girl[i] 出发
if (findPath(girl[i], boy[i])) {
cout << "Unsafe" << endl;
} else {
cout << "Safe" << endl;
}
}
总结
- 能不能做？ 能。逻辑是通的，就是检查残量网络中是否存在
的路径。 - 推荐吗？ 不推荐。
- 本质区别：
- 暴力法是：“我把这对拆了，看看能不能修补。”（重复
次） - SCC法是：“我看一眼全图的结构，把所有能互换的圈子一次性都圈出来。”（只做
次）
- 暴力法是：“我把这对拆了，看看能不能修补。”（重复
SCC 思路
这正是算法竞赛中 图论结构性质（SCC） 优于 朴素模拟（BFS/DFS） 的典型案例。
这道题（P1407 [国家集训队] 稳定婚姻）是一个非常经典的二分图匹配与**强连通分量（SCC）**结合的题目。
简单来说，之所以用 SCC，是因为判断婚姻是否“不安全”，本质上是在判断这条婚姻边是否处于二分图的一个“交替环”上。
下面我为你拆解其中的逻辑推导过程。
1. 理解“不安全”的定义
题目中定义：如果 和 离婚，且这 个人依然能重新组成 对夫妻（完美匹配），则称该婚姻是 Unsafe（不安全的）。
这意味着，原有的匹配方案并不是唯一的。只要我们能在图中找到另一组合法的完美匹配方案，且该方案不包含 这条边，那么这对夫妻就是可以被“拆散”的。
2. 图论建模：二分图与交替环
我们将人物分为左右两部：
- 左边点集： 个女方（Girl）
- 右边点集： 个男方（Boy）
图中有两种边：
- 婚姻边（实线）：，表示现在的夫妻关系。
- 旧情边（虚线）：，表示两人曾经相爱（可以私奔）。
什么是交替环？
假设现在的婚姻是 和 。 如果存在旧情关系： 爱 ， 爱 。 这就形成了一个环：
在这个环中，我们可以把婚姻边替换成旧情边：
- 原匹配：
- 新匹配：
结论： 如果一对夫妻 处于一个由“婚姻边”和“旧情边”交替组成的环（Alternating Cycle）中，那么这对夫妻就可以通过“换伴侣”的方式被拆散，婚姻就是 Unsafe 的。反之，如果不在任何环中，就是 Safe 的。
3. 为什么要转化成有向图求 SCC？
在无向图中找环比较麻烦，尤其是我们要找的是“交替”环。我们可以通过给边定向来巧妙地解决这个问题。
建图策略：
- 婚姻边（）：对于每一对现有的夫妻 ，建一条有向边 。
- 旧情边（）：对于每一对旧情人 ，建一条有向边 。
逻辑推导：
在这个有向图中，如果我们从 出发，走到了 （通过婚姻边），然后如果能从 绕一圈回到 ，就说明存在一个环。
路径大概长这样：
- 代表“原配”。
- 代表“出轨”。
如果 和 在同一个**强连通分量（SCC）**中：
- 意味着 可以到达 （显然，因为有直连边）。
- 同时也意味着 可以到达 （通过一系列的出轨和别人的原配）。
- 这就形成了一个闭环！
4. 算法流程总结
- 映射：使用
std::map将人名映射为 的整数编号。 - 建图：
- 读入 对夫妻：连边 。
- 读入 对旧情：连边 。
- Tarjan 算法：对全图跑一遍 Tarjan，求出每个点所属的强连通分量编号
scc_id[]。 - 判断：
- 对于第 对夫妻 ：
- 如果
scc_id[Girl_i] == scc_id[Boy_i]，说明他们在同一个环内 Unsafe。 - 否则 Safe。
5. 代码核心实现（C++）
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* date: 2025-12-29 21:00:20
*/
#include <bits/stdc++.h>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6+5;
const int maxe = 4e6+5;
const int mod = 1e9+7;
int n,m;
int a[maxn];
std::map<string,int> name2id;
std::vector< std::pair<int,int>> couples;
struct linkList {
typedef struct {int u,v,w,next;} edge;
edge e[maxe];
int h[maxn],edge_cnt=0;
linkList(){
reset();
}
void reset() {
edge_cnt=0;
memset(h,-1,sizeof(h));
}
//遍历点u 周围点
template<typename U>
void for_each(int u,U func){
for(int i = h[u] ; i !=-1;i = e[i].next)
func(e[i].u,e[i].v,e[i].w); //u v w
}
void add(int u,int v,int w=0){
e[edge_cnt] = {u,v,w,h[u]};
h[u] = edge_cnt++;
}
void add2(int u,int v,int w=0){
add(u,v,w);
add(v,u,w);
}
//下标访问
edge& operator[](int i){ return e[i]; }
//返回head[u]
int operator()(int u){ return h[u]; }
} e;
//oisnip_beginscc.cpp
struct TarjanScc {
int n, timer;
std::stack<int> st;
bool in_stack[maxn];
int dfn[maxn], low[maxn], scc_id[maxn];
int scc_cnt; // SCC 的总数
void set(int _n) {
n = _n;
timer = scc_cnt = 0;
memset(dfn, 0, sizeof(dfn));
memset(in_stack, 0, sizeof(in_stack));
}
// 有向图,不要加father参数
void dfs(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
in_stack[u] = true;
for (int i = e(u); ~i ; i = e[i].next) {
int v = e[i].v;
if (!dfn[v]) { // 如果 v 没被访问过
dfs(v);
// 根据子节点的 low 值更新当前节点的 low 值
low[u] = std::min(low[u], low[v]);
} else if (in_stack[v]) { //返祖边, 如果 v 在栈中，说明构成了环
low[u] = std::min(low[u], dfn[v]);
}
}
// 如果 dfn == low，说明找到了一个 SCC 的起始点
if (low[u] == dfn[u]) {
scc_cnt++;
while (1) {
int v = st.top(); st.pop();
in_stack[v] = 0;
scc_id[v] = scc_cnt; // 标记所属 SCC 编号
if (v == u) break; // 直到找到起始点
}
}
}
void print_scc_id() {
for(int i = 1;i <= n ;++i ) // i: 1->n
{
std::cout << i << " " << scc_id[i] << "\n";
}
}
void solve() {
for (int i = 1; i <= n; i++) {
if (!dfn[i]) dfs(i);
}
}
};
//oisnip_end
TarjanScc tjscc;
void init(){
std::cin >> n;
int cnt = 0;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
string gname,bname;
std::cin >> gname >> bname;
// std::cout << gname << " ";
// std::cout << bname << "\n";
name2id[gname] = ++cnt;
name2id[bname] = ++cnt;
int u = name2id[gname];
int v = name2id[bname];
// 建图核心：女 -> 男
e.add(u,v);
//存下夫妻关系
couples.push_back( std::make_pair(u, v));
}
// 处理旧情（旧情边：男 -> 女）
std::cin >> m;
for(int i = 1;i <= m ;++i ) // i: 1->m
{
string gname,bname;
std::cin >> gname >> bname;
// std::cout << gname << " ";
// std::cout << bname << "\n";
int u = name2id[bname];
int v = name2id[gname];
// 建图核心：男 -> 女
e.add(u,v);
}
}
signed main () {
ios::sync_with_stdio(false); cin.tie(0);
init();
tjscc.set(2*n);
tjscc.solve();
// tjscc.print_scc_id();
for( auto p : couples) {
if( tjscc.scc_id[p.first] == tjscc.scc_id[p.second])
std::cout << "Unsafe" << "\n";
else
std::cout << "Safe" << "\n";
}
return 0;
}
总结
这道题之所以是 SCC，是因为二分图完美匹配中的交替环等价于有向图中的强连通分量。利用 Tarjan 算法可以在 的线性时间内找出所有的环，从而快速判断每一对婚姻的安全性。