记录编号	324350	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]稳定婚姻	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	0.231 s
提交时间	2016-10-18 06:32:52	内存使用	0.75 MiB

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<stack>
using namespace std;
const int maxn=8005;
const int maxm=40005;
map<string, int>mp;
int n,m,cnt,bel[maxn],len,head[maxn],dfn[maxn],low[maxn],tim;
bool ins[maxn];
stack<int>s;
struct edge{
	int to,next;
}a[maxm];
void insert(int x,int y){
	len++;a[len].to=y;a[len].next=head[x];head[x]=len;
}
void tarjan(int x){
	tim++;dfn[x]=low[x]=tim;s.push(x);ins[x]=1;
	for(int i=head[x];i;i=a[i].next){
		int t=a[i].to;
		if(!dfn[t]){
			tarjan(t);
			low[x]=min(low[x],low[t]);
		}
		else if(ins[t])low[x]=min(low[x],dfn[t]);
	}
	if(dfn[x]==low[x]){
		cnt++;
		int k;
		do{
			k=s.top();s.pop();
			ins[k]=0;bel[k]=cnt;
		}while(k!=x);
	}
}
int main(){
	freopen("marriage.in","r",stdin);
	freopen("marriage.out","w",stdout);
	scanf("%d", &n);
	char s1[15], s2[15];
	for (int i=1;i<=n;i++){
		scanf("%s%s",s1,s2);
		insert(i*2-1,i*2);
		mp[s1]=i*2-1;
		mp[s2]=i*2;
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++){
		scanf("%s%s",s1,s2);
		insert(mp[s2], mp[s1]);
	}
	for (int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
	for (int i=1;i<=n;i++){
		if (bel[i*2-1]== bel[i*2]) printf("Unsafe\n");
		else printf("Safe\n");
	}
}