题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2140
思路：
很明显的二分图匹配的模型题（首先每个人看成一个点，男女分别分成两个集合，关系用点之间的连边来表示即可），对于每对婚姻关系是否稳定，其实可以转化为二分图中对应的边是否为关键匹配边（即删去该边之后最大匹配数是否仍然是n），如果是关键匹配边就是“Safe”，否则就是"Unsafe"。
对于求关键匹配边，明显直接删边然后跑最大匹配是行不通的，即使是最快的二分图匹配算法也要达到O(nmsqrt(n))的复杂度。所以，我们只能从其他方面入手：首先用网络流求一次最大匹配，然后在残量网络中用Tarjan算法求强连通分量，如果对于一个匹配边(s,t)，有s，t在同一个SCC（或者是该边未满流），那么这条边就不是最大匹配边，反之就是。（因为如果在同一SCC中，这条匹配边就可以用该边所在SCC中另外一条匹配边代替。）复杂度O（n^2 m+n+m）（虽然这个复杂度比上面的****O(nmsqrt(n))高不少，但是由于网络流算法sap虽然复杂度高达O(n^2 m)，但是优化后在实践中却相当快，与HLPP相差不了多少，所以后者的速度其实比前者快很多，可以解决该题****）****
****代码（代码较长，我在处理名字方面凶残的用了Trie。。。）：****
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 8010
#define inf 0x7fffffff
struct edge{
int t,f;
edge *next,*pair;
edge (){
next=pair=NULL;
}
}*head[MAXN];
void Add(int s,int t,int f){
edge *p=new(edge);
p->t=t,p->f=f,p->next=head[s];
head[s]=p;
}
void AddEdge(int s,int t,int f){
Add(s,t,f),Add(t,s,0);
head[s]->pair=head[t],head[t]->pair=head[s];
}
int n,m,V=0,S,T;
int Couple[MAXN][2];
string s1,s2;
edge *E[MAXN];
string getstring(){
string s="";
int c;
for(c=getchar();!((c>=int('a')&&c<=int('z'))||(c>=int('A')&&c<=int('Z')));c=getchar());
s=s+char(c);
for(c=getchar();(c>=int('a')&&c<=int('z'))||(c>=int('A')&&c<=int('Z'));c=getchar()) s=s+char(c);
return s;
}
struct node{
node *child[52];
int v;
node (){
memset(child,0,sizeof(child));
}
}*roof=NULL;
int Trans(char c){
if(c>='a'&&c<='z')return int(c)-int('a');
return int(c)-int('A')+26;
}
int Insert(string c,int p,node*&t){
if(!t) t=new(node);
if(p==c.size())return t->v=++V;
return Insert(c,p+1,t->child[Trans(c[p])]);
}
int Search(string c,int p,node *t){
if(p==c.size())return t->v;
return Search(c,p+1,t->child[Trans(c[p])]);
}
void INIT(){
memset(head,0,sizeof(head));
scanf("%d",&n);
for(int i=0;i++<n;){
s1=getstring();
s2=getstring();
Couple[i][0]=Insert(s1,0,roof);
Couple[i][1]=Insert(s2,0,roof);
}
S=++V;T=++V;
for(int i=0;i++<n;){
AddEdge(Couple[i][0],Couple[i][1],1);
E[i]=head[Couple[i][0]];
AddEdge(S,Couple[i][0],1),AddEdge(Couple[i][1],T,1);
}
scanf("%d",&m);
while(m--){
int v1,v2;
s1=getstring();
s2=getstring();
v1=Search(s1,0,roof),v2=Search(s2,0,roof);
AddEdge(v1,v2,1);
}
}
int h[MAXN],gap[MAXN];
edge *d[MAXN];
int sap(int v,int flow){
if(v==T)return flow;
int rec=0;
for(edge *p=d[v];p;p=p->next)if(h[v]==h[p->t]+1&&p->f){
int ret=sap(p->t,min(flow-rec,p->f));
p->f-=ret,p->pair->f+=ret;
d[v]=p;
if((rec+=ret)==flow)return flow;
}
if(!(--gap[h[v]])) h[S]=T;
gap[++h[v]]++;
d[v]=head[v];
return rec;
}
void maxflow(){
memset(h,0,sizeof(h));
memset(gap,0,sizeof(gap));
gap[0]=T;
for(int i=0;i++<T;) d[i]=head[i];
while(h[S]<T)sap(S,inf);
}
int dfn[MAXN],low[MAXN],Index=0,Scc=0,Id[MAXN];
bool f[MAXN];
stack<int>St;
void Tarjan(int v){
dfn[v]=low[v]=++Index;
St.push(v),f[v]=true;
for(edge *p=head[v];p;p=p->next)if(p->f){
if(!dfn[p->t]){
Tarjan(p->t);
low[v]=min(low[v],low[p->t]);
}else{
if(f[p->t]){
low[v]=min(low[v],low[p->t]);
}
}
}
if(low[v]==dfn[v]){
Scc++;
int u;
do{
u=St.top();
St.pop();
f[u]=false;
Id[u]=Scc;
}while(u!=v);
}
}
void Solve(){
memset(dfn,0,sizeof(dfn));
memset(f,false,sizeof(f));
while(!St.empty()) St.pop();
for(int i=0;i++<T;)if(!dfn[i])Tarjan(i);
for(int i=0;i++<n;){
if(Id[Couple[i][0]]==Id[Couple[i][1]]||E[i]->f)printf("Unsafe\n")
; else printf("Safe\n");
}
}
int main(){
INIT();
maxflow();
Solve();
return 0;
}
