记录编号	143016	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]稳定婚姻	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.246 s
提交时间	2014-12-12 14:35:29	内存使用	0.54 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
using namespace std;
const int SIZEN=8010;
int N,M;
vector<int> c[SIZEN];
void addedge(int a,int b){
	c[a].push_back(b);
}
int dfn[SIZEN],timer=0;
int low[SIZEN];
stack<int> ST;
bool instack[SIZEN];
int belong[SIZEN];
void Tarjan(int x){
	if(dfn[x]) return;
	dfn[x]=low[x]=++timer;
	ST.push(x);
	instack[x]=true;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(!dfn[u]){
			Tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		else if(instack[u]) low[x]=min(low[x],dfn[u]);
	}
	if(dfn[x]==low[x]){
		int now;
		do{
			now=ST.top();
			belong[now]=x;
			instack[now]=false;
			ST.pop();
		}while(now!=x&&!ST.empty());
	}
}
map<string,int> lis;
int size[SIZEN];
void work(void){
	for(int i=1;i<=N;i++)
		if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=N;i++) size[belong[i]]++;
	for(int i=1;i<=N;i++){
		if(size[belong[i]]==1) printf("Safe\n");
		else printf("Unsafe\n");
	}
}
void read(void){
	scanf("%d",&N);
	char name[10]={0},a[10]={0},b[10]={0};
	for(int i=1;i<=N;i++){
		scanf("%s",name);
		lis[name]=i;
		scanf("%s",name);
		lis[name]=i;
	}
	scanf("%d",&M);
	for(int i=1;i<=M;i++){
		scanf("%s%s",a,b);//a女b男
		addedge(lis[a],lis[b]);
	}
}
int main(){
	freopen("marriage.in","r",stdin);
	freopen("marriage.out","w",stdout);
	read();
	work();
	return 0;
}