先来强化一下强连通分量
luogu P1407 [国家集训队] 稳定婚姻
题意：
给n对现在的夫妻和m对曾经相爱的人。
如果有一对夫妻分开了，有没有可能这两个人和另外的几对夫妻组成新的组合。
如果可能输出‘unsafe’，否则输出‘safe’
思路：
看完题之后我懵了，我看了一眼题解描述的题意才明白这个题是什么意思。
“我们尝试着将所有的丈夫和妻子用线段连接起来，表示他们之间存在着联系，如果这时有一个女孩和其中的丈夫交往过，那么他们之间也存在着这种联系，所以这两种情况我们可以认为本质是相同的。
那么我们将所有 现在或曾经交往过的 男孩和女孩连接起来，可以发现出现了一些环，而处在环中的几对夫妻都可以更换伴侣，也就是题目中所说的婚姻不安全。那么我们找出这些环，判断哪些夫妻处在环中即可。”
看了这段话恍然大悟，其实就是找环，跟强连通分量一联系，才发现，tarjan算法的实质就是有向图找环
对于这个题来说还要变形一下，因为夫妻和曾经的恋人本来就是两个元素的小环，那么一定有环，
又看了一眼博主的题解，真的妙。
这样既能避免原有的环，又能找到新的环。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int>e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top; // 栈的作用是记录正在访问的点
int scc[N], siz[N], cnt; //最后的结果是scc[i] = k 记录第i个节点在第k个强连通分量里，大小是siz【k】
bool Safe[N];
void tarjan(int x) {
//入x时， 盖戳， 入栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y : e[x]) {
if(!dfn[y]) { //若y尚未访问
tarjan(y);
low[x] = min(low[x], low[y]); //回x时更新low
}
else if(instk[y]) { //若y已访问且在栈中
low[x] = min(low[x], low[y]);
}
// 剩下已经访问并且不在栈中的情况是y已经被访问完，不在枚举
}
//离x时，记录scc
if(dfn[x] == low[x]) { //若x是scc的根
int y; ++cnt;
vector<int>vt;
// vt.push_back(x);
do{ //陆续把强连通分量出栈
y = stk[top--]; instk[y] = 0;
scc[y] = cnt; //scc编号
vt.push_back(y);
++siz[cnt]; //scc大小
} while(y != x);
if(vt.size() != 1) {
for (auto it : vt) {
Safe[it] = 1;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n;
map<string, int>mp;
int id = 1;
for (int i = 0; i < n; i++) {
string s, t;
cin >> s >> t;
mp[s] = id++;
mp[t] = id++;
e[mp[s]].push_back(mp[t]);
}
cin >> m;
for (int i = 0; i < m; i++) {
string s, t;
cin >> s >> t;
e[mp[t]].push_back(mp[s]);
}
for (int i = 1; i <= n * 2; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n * 2; i += 2) {
if(Safe[i]) {
cout << "Unsafe\n";
}
else {
cout << "Safe\n";
}
}
return 0;
}