题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2140
模拟的时候考了这个题，考场上没想到tarjan，就打算写个暴力跑路，结果居然过了…
按照题意模拟…大体上就相当于跑一遍二分图匹配
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<bits/stdc++.h> #define maxn 4040 #define inf 1000000007 #define pb push_back using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m,tot; int a[maxn],b[maxn],belong[maxn*2]; map<string,int>mp; vector<int>go[maxn*2]; bool vis[maxn*2]; inline void init(){ n=rd(); for(int i=1; i<=n; i++){ string s1,s2; cin>>s1>>s2; if(!mp[s1])mp[s1]=++tot; if(!mp[s2])mp[s2]=++tot; a[i]=mp[s1],b[i]=mp[s2]; } m=rd(); while(m--){ string s1,s2; cin>>s1>>s2; int x=mp[s1],y=mp[s2]; go[x].pb(y); } } bool find(int now){ for(int i=0; i<go[now].size(); i++){ int to=go[now][i]; if(vis[to])continue; vis[to]=true; if(!belong[to] || find(belong[to])){ belong[to]=now; return true; } } return false; } inline void work(){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++)belong[b[j]]=a[j]; belong[b[i]]=0; memset(vis,0,sizeof(vis)); if(!find(a[i]))puts("Safe"); else puts("Unsafe"); } } int main(){ //freopen("d.in","r",stdin); init(); work(); return 0; } |