首先我们考虑用图论的边描述这个关系。若两者存在夫妻或情侣关系，就连一条边（是有向边还是无向边呢？）。
先来考虑两对夫妻的情况，若夫妻边与情侣边交替出现。且一对夫妻在同一个环内，则可以说明分开后能够重新找到另一半。
如下图：
夫妻
a-男 b-女
c-男 d-女
情侣
a-男 d-女
c-男 b-女
为什么一定要夫妻边和情侣边交替出现呢？因为只有在这种情况下，a可以找到d，b可以找到c，即原来的夫妻全都可以通过相邻的情侣边找到新的另一半。
但是对于不交替出现的情况，显然是不能实现的，这里手搓一下就行。
那么对于夫妻边，建一条由男指向女的边；情侣边，建一条由女指向男的边，这样走出来的一条环就一定是两种边交替出现的。
最后判断一对夫妻是否在同一个强连通分量中即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
const int N=1e5;
int n,m;
string a[N],b[N];
int cnt_name;
map<string,int> name;
int tot=1,nxt[N],to[N],h[N];
void add(int x,int y) {
to[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
}
int dfn[N],low[N],id[N],fst[N];
int scc_cnt,timestamp;
stack<int> st;
void tarjan(int nd) {
dfn[nd]=low[nd]=++timestamp;
st.push(nd); fst[nd]=1;
for(int i=h[nd];i;i=nxt[i]) {
int x=to[i];
if(!dfn[x]) {
tarjan(x);
low[nd]=min(low[nd],low[x]);
}
else if(fst[x]) low[nd]=min(low[nd],dfn[x]);
}
if(dfn[nd]==low[nd]) {
int y;
scc_cnt++;
do {
y=st.top(); st.pop();
id[y]=scc_cnt; fst[y]=0;
} while(y!=nd);
}
}
int main() {
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i]>>b[i];
name[a[i]]=++cnt_name;
name[b[i]]=++cnt_name;
add(name[a[i]],name[b[i]]);
}
cin>>m;
for(int i=1;i<=m;i++) {
string x,y; cin>>x>>y;
add(name[y],name[x]);
}
for(int i=1;i<=2*n;i++) {
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;i++) {
int x=id[name[a[i]]],y=id[name[b[i]]];
if(x==y) cout<<"Unsafe"<<"\n";
else cout<<"Safe\n";
}
return 0;
}