在洛谷中查看
题意：
自己读一下，大致就是 \(2n\) 个点，每个点编号为 \(1 - 2n\)，\(\lfloor 编号/2 \rfloor\) 相同的点连条边。
然后再给 \(m\) 条边。
问：将每个 \(\lfloor 编号/2 \rfloor\) 相同的点间连的边断开，还能不能使每个 编号为奇数的点 都有一个 编号为偶数的点 对应。
这个不太好讲，你们自己看看题呗 q(≧▽≦q)。
思路：
这一篇题解讲得挺好的，我就给你们讲下为什么吧。
大致的思考路线就是：
-
第 \(i\) 对婚姻不安全，就说明：\(B_i\) 和 \(G_i\) 在同一个强连通分量里。
证明：每条边连的两个点一定一男一女嘛（一奇一偶）。那么如果构成了环，那环上的点数一定是偶数，所以每个人都能找到其他配偶。 -
那就只用看能不能构成环了嘛，考虑用 Tarjan 求。
PS:评论区有 dalao 说用点双联通，但我还不会，只能讲讲我会的。以后学了再来试试吧。
如果这第 \(i\) 对夫妻在同一个强连通分量里，则是不安全的婚姻。所以缩个点就行，但问题来了，不能在无向图缩啊（所以有 dalao 说用点双）。
那我们需要将它转换成有向图。
dalao 的题解里说了。
- 夫妻之间：\(girl\) → \(boy\)
- 情人之间：\(boy\) → \(girl\)
但为什么呢，其实很好想，自己画个图就知道了。
如果都 \(girl\) → \(boy\) 或 \(boy\) → \(girl\)，那某些点出度就为 \(0\) 了，找不了其他恋人了。
Code:
(这次没什么注释，我觉得挺好理解的，如果你没懂，直接喊我，或 QQ 问，我会解答的，题解就是为了讲明白，谢谢~)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8e3+5;
int n,m,dfn[N],low[N],num,cnt,col[N],st[N],top;
string boy,girl;
vector<int> g[N],color[N];
map<string,int> cur;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
return s*f;
}
void tarjan(int x){
dfn[x]=low[x]=++num;st[++top]=x;
for(int i=0;i<g[x].size();i++){
int t=g[x][i];
if(!dfn[t])tarjan(t),low[x]=min(low[x],low[t]);
else if(!col[t])low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x])for(cnt++;st[top+1]!=x;top--)col[st[top]]=cnt,color[cnt].push_back(st[top]);
}
int main(){
/*
solution:
对于n对夫妻，我们将男的连向
*/
n=read();
for(int i=1;i<=n;i++){
cin>>girl>>boy;
cur[girl]=i*2-1;cur[boy]=i*2;
g[cur[girl]].push_back(cur[boy]);
}
m=read();
for(int i=1;i<=m;i++){
cin>>girl>>boy;
g[cur[boy]].push_back(cur[girl]);//不同于上面，连的方向相反
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++){
if(col[i*2-1]==col[i*2])cout<<"Unsafe\n";
else cout<<"Safe\n";
}
return 0;
}