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

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N = 8005;
const int M = 40005;
map<string, int>mp;
int n, m, tot, f[N], cntt, siz[N], bel[N];
int to[M], nxt[M], lj[N], w[M], cnt;
void add(int f, int t){
	cnt++;//计数器
	to[cnt] = t;//下个顶点的坐标
	nxt[cnt] = lj[f];//前一个
	lj[f] = cnt;//后一个
}
int st[M * 4], h, dfn[N], low[N], Tar;
bool ins[N], flag, b[N];
void pop(){
	ins[st[h]] = false;
	bel[st[h]] = tot;
	h--;
}
void Tarjan(int x)
{
	dfn[x] = low[x] = ++Tar;//深度搜索的步数
	st[++h] = x;//入栈
	ins[x] = true;//访问过
	for (int i = lj[x]; i; i = nxt[i])
	{
		if (!dfn[to[i]])//没有访问过
		{
			Tarjan(to[i]);//深度搜索
			low[x] = min(low[x], low[to[i]]);//
		}
		else if (ins[to[i]]) low[x] = min(low[x], dfn[to[i]]);//在栈中 没有被访问过
	}
	if (dfn[x] == low[x])
	{
		tot++;
		while (st[h] != x) pop();//出栈操作并把ins标记为f，bel【】等于tot  在一个强连通领域中
		pop();
	}
}
int main()
{
	freopen("marriage.in","r",stdin);
	freopen("marriage.out","w",stdout);
	scanf("%d", &n);
	char c[15], s[15];
	for (int i=1;i<=n;i++){
		scanf("%s%s", c, s);
		add(i * 2 - 1, i * 2);
		mp[c] = i * 2 - 1;
		mp[s] = i * 2;
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%s%s", c, s);
		add(mp[s], mp[c]);
	}
	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");
	}
}