大佬们，求回复
by 美少女☁ @ 2021-02-23 19:55:17
@[美少女☁](/user/445864)
```cpp
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
const int N = 500000;
int n,m;
int maxn;
int h[N],e[N],ne[N],idx;
int match[N];
int vis[N];
map<string,int > mp;
int xh;
int A,B;
void insert(int a,int b);
bool find(int now);
int main()
{
cin>>n;
memset(h,-1,sizeof(h));
for(int i=1;i<=n;i++)
{
string a,b;
cin>>a>>b;
mp[a] = ++xh; //注意这里的编号方式
mp[b] = ++xh;
match[mp[a]] = mp[b];
match[mp[b]] = mp[a];
insert(mp[a],mp[b]);
}
cin>>m;
for(int i=1;i<=m;i++)
{
string a,b;
cin>>a>>b;
insert(mp[a],mp[b]);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
A =(i-1)*2+1;B = match[A]; //编号对应
match[B] = 0;
if(find((i-1)*2+1)) cout<<"Unsafe"<<endl; //同上
else cout<<"Safe"<<endl;
match[B] = A;
}
return 0;
}
void insert(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool find(int now)
{
for(int i=h[now];i!=-1;i=ne[i])
{
int spot = e[i];
if(now==A&&spot==B) continue;
if(vis[spot]==0)
{
vis[spot] = 1;
if(match[spot]==0||find(match[spot]))
{
//match[spot] = now; //不用改变匹配关系，否则跑一遍就全乱了
return true; //因为当前只有一个始作俑者，并且右边每个点只查一次
} //所以不用记录当前匹配者，只返回成功与否就行
}
}
return false;
}
```
by yxy_ @ 2021-05-30 15:42:45