自动搬运

查看原文

来自洛谷，原作者为

	雨季 **

搬运于2025-08-24 21:24:44，当前版本为作者最后更新于2018-03-13 07:21:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

我们尝试着将所有的丈夫和妻子用线段连接起来，表示他们之间存在着联系，如果这时有一个女孩和其中的丈夫交往过，那么他们之间也存在着这种联系，所以这两种情况我们可以认为本质是相同的。
那么我们将所有 现在或曾经交往过的 男孩和女孩连接起来，可以发现出现了一些环，而处在环中的几对夫妻都可以更换伴侣，也就是题目中所说的婚姻不安全。那么我们找出这些环，判断哪些夫妻处在环中即可。
对于找环，我们想到了$Tarjan$求强连通分量，但是这个算法是在有向图上进行的，于是我们尝试给我们连接出的无向图定向，发现只要按照 $...$男$\to$女$\to$男$\to$女$...$ 的顺序，男女交替就可以$Tarjan$判出环来。
所以我们可以这样建图：

• 夫妻之间：$girl \to boy$
• 情人之间：$boy \to girl$

$Tarjan$求强连通分量，对于一对夫妻，如果两人在同一个强连通分量里，那么这对婚姻就是不安全的，反之，则是安全的。

代码

#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;
}