WA 二分图求调 玄二关
查看原帖
WA 二分图求调 玄二关
768270
__why楼主2024/7/18 19:08
#include<bits/stdc++.h>
using namespace std;
const int maxn = 8e3+5;
int n,m,cnt;
map<string,int>mp;
vector<int>a[maxn];
int vis[maxn],match[maxn],men[maxn];
bool dfs(int x){
	for(auto i : a[x]){
		if(!vis[i]){
			vis[i] = 1;
			if(match[i]==0||dfs(match[i])){
				return true;
			}
		}
	}
	return false;
}
int num(string s){
	mp[s];
	if(!mp[s])mp[s] = ++cnt;
	return mp[s];
}
int main(){
	cin>>n;
	string boy,girl;
	for(int i = 1;i<=n;i++){
		cin>>boy>>girl;
		a[num(boy)].push_back(num(girl));
		match[num(boy)] = match[num(girl)];
		match[num(girl)] = match[num(boy)];
		men[num(boy)] = 1;
	}
	cin>>m;
	for(int i = 1;i<=m;i++){
		cin>>boy>>girl;
		a[num(boy)].push_back(num(girl));
	}
	for(int i = 1;i<=cnt;i++)if(men[i]){
		memset(vis,0,sizeof vis);
		match[match[i]] = 0;
		if(dfs(i))cout<<"Unsafe"<<endl;
		else cout<<"Safe"<<endl;
		match[match[i]] = i;
	}
}
2024/7/18 19:08
加载中...