题解 P1407 【[国家集训队]稳定婚姻【重题P2397】】
雨季
·
·
题解
题解
我们尝试着将所有的丈夫和妻子用线段连接起来，表示他们之间存在着联系，如果这时有一个女孩和其中的丈夫交往过，那么他们之间也存在着这种联系，所以这两种情况我们可以认为本质是相同的。
那么我们将所有 现在或曾经交往过的 男孩和女孩连接起来，可以发现出现了一些环，而处在环中的几对夫妻都可以更换伴侣，也就是题目中所说的婚姻不安全。那么我们找出这些环，判断哪些夫妻处在环中即可。
对于找环，我们想到了Tarjan求强连通分量，但是这个算法是在有向图上进行的，于是我们尝试给我们连接出的无向图定向，发现只要按照 ...男\to女\to男\to女... 的顺序，男女交替就可以Tarjan判出环来。
所以我们可以这样建图：
- 夫妻之间：girl \to boy
- 情人之间：boy \to girl
# 代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;
#define N 10005
#define M 300005
int n,m;
map<string,int>cou; // couple
struct node {
int v,nex;
}e[M];
int tot,h[N];
void add(int u,int v) {
e[++tot].v=v;
e[tot].nex=h[u];
h[u]=tot;
}
inline int read() {
int tmp=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') tmp=(tmp<<1)+(tmp<<3)+ch-'0',ch=getchar();
return tmp;
}
bool ins[N];
int s[N],top;
int cnt,belong[N];
int dfn[N],low[N],idx;
void Tarjan(int u) {
dfn[u]=low[u]=++idx;
s[++top]=u;
ins[u]=1;
for(int i=h[u];i;i=e[i].nex) {
int v=e[i].v;
if(!dfn[v]) {
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
++cnt;
do{
belong[s[top]]=cnt;
ins[s[top]]=0;
}while(s[top--]!=u);
}
}
int main()
{
n=read();
string gir,boy;
for(int i=1;i<=n;++i) {
cin>>gir>>boy;
cou[gir]=i;
cou[boy]=i+n;
add(i,i+n);
}
m=read();
for(int i=1;i<=m;++i) {
cin>>gir>>boy;
add(cou[boy],cou[gir]);
}
for(int i=1;i<=n*2;++i) if(!dfn[i]) Tarjan(i);
for(int i=1;i<=n;++i) {
if(belong[i]==belong[i+n]) printf("Unsafe\n");
else printf("Safe\n");
}
return 0;
}
```