Tarjan 例题:洛谷P1407 [国家集训队] 稳定婚姻

发布时间 2023-08-11 13:19:24作者: 今添

在洛谷中查看


题意:

自己读一下,大致就是 \(2n\) 个点,每个点编号为 \(1 - 2n\)\(\lfloor 编号/2 \rfloor\) 相同的点连条边。
然后再给 \(m\) 条边。
问:将每个 \(\lfloor 编号/2 \rfloor\) 相同的点间连的边断开,还能不能使每个 编号为奇数的点 都有一个 编号为偶数的点 对应。

这个不太好讲,你们自己看看题呗 q(≧▽≦q)。

思路:

一篇题解讲得挺好的,我就给你们讲下为什么吧。

大致的思考路线就是:

  1. \(i\) 对婚姻不安全,就说明:\(B_i\)\(G_i\) 在同一个强连通分量里。
    证明:每条边连的两个点一定一男一女嘛(一奇一偶)。那么如果构成了环,那环上的点数一定是偶数,所以每个人都能找到其他配偶。

  2. 那就只用看能不能构成环了嘛,考虑用 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;
}