Problem
我们已知n对夫妻的婚姻状况,称第i对夫妻的男方为Bi,女方为Gi。若某男Bi与某女Gj曾经交往过(无论是大学,高中,亦或是幼儿园阶段,i≠j),则当某方与其配偶(即Bi与Gi或Bj与Gj)感情出现问题时,他们有私奔的可能性。不妨设Bi和其配偶Gi感情不和,于是Bi和Gj旧情复燃,进而Bj因被戴绿帽而感到不爽,联系上了他的初恋情人Gk……一串串的离婚事件像多米诺骨牌一般接踵而至。若在Bi和Gi离婚的前提下,这2n个人最终依然能够结合成n对情侣,那么我们称婚姻i为不安全的,否则婚姻i就是安全的。给定所需信息,你的任务是判断每对婚姻是否安全。
第一行为一个正整数n,表示夫妻的对数; 以下n行,每行包含两个字符串,表示这n对夫妻的姓名(先女后男),由一个空格隔开; 第n+2行包含一个正整数m,表示曾经相互喜欢过的情侣对数; 以下m行,每行包含两个字符串,表示这m对相互喜欢过的情侣姓名(先女后男),由一个空格隔开。 所有姓名字符串中只包含英文大小写字母,大小写敏感,长度不大于8, 保证每对关系只在输入文件中出现一次,输入文件的最后m行不会出现未在之前出现过的姓名, 这2n个人的姓名各不相同
输出文件共包含n行,第i行为“Safe”(如果婚姻i是安全的)或“Unsafe”(如果婚姻i是不安全的)。
Solution
二分图,夫妻女向男连边,旧情男向女连边,如果夫妻二人在同一个强连通分量内,那么找到夫妻男到女的一个环,关系在环上转移一下就离婚了,因此只需要求强连通分量即可。
Code
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 70 71 72 73 74 75 76 77 78 79
| #include<stdio.h> #include<iostream> #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; #include<string> #include<stack> #include<map> #include<vector> const int MAXN=10020; const int MAXM=50020; int n,m,idx,cnt; int dfn[MAXN]; int low[MAXN]; bool instack[MAXN]; int g[MAXN]; struct E{ int u,v,nex; }e[MAXM]; stack<int>s; vector<int>belong[MAXN]; void Tarjan(int u){ dfn[u]=low[u]=++idx; s.push(u); instack[u]=true; for(int i=g[u];i>0;i=e[i].nex){ int v=e[i].v; if(!dfn[v]){ Tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ ++cnt; int cur; do{ cur=s.top();s.pop(); instack[cur]=false; belong[cnt].push_back(cur); }while(cur!=u); } } map<string,int>mp; int num; int name[2*MAXN]; int main(){ io_opt; cin>>n; string x,y; for(int i=1;i<=n;i++){ cin>>x>>y; if(!mp[x]) mp[x]=++num; if(!mp[y]) mp[y]=++num; int xx=mp[x],yy=mp[y]; name[2*i-1]=xx; name[2*i]=yy; e[i]=(E){xx,yy,g[xx]};g[xx]=i; } cin>>m; for(int i=n+1;i<=n+m;i++){ cin>>x>>y; int xx=mp[x],yy=mp[y]; e[i]=(E){yy,xx,g[yy]};g[yy]=i; } for(int i=1;i<=num;i++){ if(!dfn[i]) Tarjan(i); } for(int i=1;i<=n;i++){ if(low[name[2*i-1]]==low[name[2*i]]){ cout<<"Unsafe"<<endl; } else{ cout<<"Safe"<<endl; } } return 0; }
|